Month: August 2013

A competitive iterative procedure using a time-indexed model for solving flexible job shop scheduling problems

  • Torgny Almgren
  • Michael Patriksson
  • Ann-Brith Strömberg
  • Karin Thörnblad
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Scheduling Tags , , , , , ,

    We investigate the efficiency of a discretization procedure utilizing a time-indexed mathematical optimization model for finding accurate solutions to flexible job shop scheduling problems considering objectives comprising the makespan and the tardiness of jobs, respectively. The time-indexed model is used to find solutions to these problems by iteratively employing time steps of decreasing length. The … Read more

    Approximate Dynamic Programming for a Class of Long-Horizon Maritime Inventory Routing Problems

  • Myun-Seok Cheon
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • Joel Sokol
    • Categories Production and Logistics, Supply Chain Management, Transportation Tags , , , ,

    We study a deterministic maritime inventory routing problem with a long planning horizon. For instances with many ports and many vessels, mixed-integer linear programming (MIP) solvers often require hours to produce good solutions even when the planning horizon is 90 or 120 periods. Building on the recent successes of approximate dynamic programming (ADP) for road-based … Read more

    A hybrid proximal extragradient self-concordant primal barrier method for monotone variational inequalities

  • Renato D.C. Monteiro
  • Benar Fux Svaiter
  • Mauricio Romero
    • Categories Complementarity and Variational Inequalities Tags ,

    In this paper we present a primal interior-point hybrid proximal extragradient (HPE) method for solving a monotone variational inequality over a closed convex set endowed with a self-concordant barrier and whose underlying map has Lipschitz continuous derivative. In contrast to the method of “R. D. C. Monteiro and B. F. Svaiter, Iteration-Complexity of a Newton … Read more

    Approximate cone factorizations and lifts of polytopes

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave … Read more

    Algebraic rules for quadratic regularization of Newton’s method

  • Elizabeth Wegner Karas
  • Sandra Augusta Santos
  • Benar Fux Svaiter
    • Categories Unconstrained Optimization Tags , , , ,

    In this work we propose a class of quasi-Newton methods to minimize a twice differentiable function with Lipschitz continuous Hessian. These methods are based on the quadratic regularization of Newton’s method, with algebraic explicit rules for computing the regularizing parameter. The convergence properties of this class of methods are analysed. We show that if the … Read more

    A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

  • Etienne de Klerk
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the … Read more

    Rational sums of hermitian squares of free noncommutative polynomials

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , , ,

    In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. … Read more

    A game-theoretic approach to computation offloading in mobile cloud computing

  • Valeria Cardellini
  • Francisco Facchinei
  • Veronica Piccialli
  • Vittoria De Nitto Persone'
  • Valerio Di Valerio
  • Vincenzo Grassi
  • Francesco Lo Presti
    • Categories Applications - OR and Management Sciences, Complementarity and Variational Inequalities, Game Theory

    We consider a three-tier architecture for mobile and pervasive computing scenarios, consisting of a local tier of mobile nodes, a middle tier (cloudlets) of nearby computing nodes, typically located at the mobile nodes access points but characterized by a limited amount of resources, and a remote tier of distant cloud servers, which have practically infinite … Read more

    Scheduling of Two Agents Task Chains with a Central Selection Mechanism

  • Alessandro Agnetis
  • Gaia Nicosia
  • Ulrich Pferschy
  • Andrea Pacifici
    • Categories Combinatorial Optimization, Game Theory, Scheduling Tags , , ,

    In this paper we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we … Read more