Linear, Cone and Semidefinite Programming

A strong conic quadratic reformulation for machine-job assignment with controllable processing times

  • M. Selim Akturk
  • Alper Atamturk
  • Sinan Gurel
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based on only the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation. CitationAppeared in Operations Research Letters. … Read more

    Semidefinite Representation of Convex Sets

  • J. William Helton
  • Jiawang Nie
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , , , , , , , ,

    Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more

    Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

  • Etienne de Klerk
  • Renata Sotirov
    • Categories Semi-definite Programming Tags ,

    We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB – a quadratic assignment problem … Read more

    A polynomial predictor-corrector trust-region algorithm for linear programming

  • Guanghui Lan
  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Nonlinear Optimization Tags , , , ,

    In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more

    On the Extension of a Mehrotra-Type Algorithm for Semidefinite Optimization

  • Mohammad Koualei
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra’s predictor-corrector algorithm that was proposed by Salahi et al. (2005) for linear optimization problems. Based on the NT (Nesterov and Todd 1997) direction as … Read more

    On the probabilistic complexity of finding an approximate solution for linear programming

  • Jun Ji
  • Florian A. Potra
    • Categories Linear Programming

    We consider the problem of finding an $\epsilon-$optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most $\epsilon$ from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained … Read more

    Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations

  • Franz Rendl
  • Giovanni Rinaldi
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming

    In this paper we present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting, that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of … Read more

    Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming

  • Kurt M. Anstreicher
    • Categories Global Optimization Theory, Semi-definite Programming Tags , ,

    We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that … Read more

    Gap, cosum, and product properties of the $\theta’$ bound on the clique number

  • Immanuel M. Bomze
  • Marco Locatelli
  • Florian Frommlet
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    In a paper published 1978, McEliece, Rodemich and Rumsey improved Lov\’asz’ bound for the Maximum Clique Problem. This strengthening has become well-known under the name Lov\’asz-Schrijver bound and is usually denoted by $\theta’$. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound … Read more

    A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Transportation Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have various capacities and fixed costs. The columns in the formulation are associated to $q$-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, … Read more