MPC

MPC 2013, ISSUE 1



Mathematical Programming Computation, Volume 5, Issue 1, March 2013

Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

Anders Skajaa, Erling D. Andersen, Yinyu Ye

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity.We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30–75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.

Full Text: PDF



Mathematical Programming Computation, Volume 5, Issue 1, March 2013

The time dependent traveling salesman problem: polyhedra and algorithm

Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, Eduardo Uchoa

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP.We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts.We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.

Full Text: PDF



Mathematical Programming Computation, Volume 5, Issue 1, March 2013

Implementation of a unimodularity test

Matthias Walter, Klaus Truemper

This paper describes implementation and computational results of a polynomial test of total unimodularity. The test is a simplified version of a prior method. The program also decides two related unimodularity properties. The software is available free of charge in source code form under the Boost Software License.

Full Text: PDF



Mathematical Programming Computation, Volume 5, Issue 1, March 2013

Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints

I. R. de Farias Jr, E. Kozyreff, R. Gupta, M. Zhao

We report and analyze the results of our computational testing of branchand-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides evaluating the performance of the cuts, we evaluate the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze results on piecewise linear optimization problems with semi-continuous constraints.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).