MPC

MPC 2016, ISSUE 2



Mathematical Programming Computation, Volume 8, Issue 2, June 2016

A practical volume algorithm

Ben Cousins, Santosh Vempala

We present a practical algorithm for computing the volume of a convex body with a target relative accuracy parameter ?>0. The convex body is given as the intersection of an explicit set of linear inequalities and an ellipsoid. The algorithm is inspired by the volume algorithms in Lovász and Vempala (J Comput Syst Sci 72(2):392–417, 2006) and Cousins and Vempala (SODA, pp. 1215–1228, 2014), but makes significant departures to improve performance, including the use of empirical convergence tests, an adaptive annealing scheme and a new rounding algorithm. We propose a benchmark of test bodies and present a detailed evaluation of our algorithm. Our results indicate that that volume computation and integration might now be practical in moderately high dimension (a few hundred) on commodity hardware.

Full Text: PDF



Mathematical Programming Computation, Volume 8, Issue 2, June 2016

Communication protocols for options and results in a distributed optimization environment

Horand Gassmann, Jun Ma, Kipp Martin

Much has been written about optimization instance formats. The MPS standard for linear mixed-integer programs is well known and has been around for many years. Other extensible formats are available for other optimization categories such as stochastic and nonlinear programming. However, the problem instance is not the only piece of information shared between the instance generator and the solver. Solver options and solver results must also be communicated. To our knowledge there is no commonly accepted format for representing either solver options or solver results. In this paper we propose a framework and theory for solver option and solver result representation in a modern distributed computing environment. A software implementation of the framework is available as an open-source COIN-OR project.

Full Text: PDF



Mathematical Programming Computation, Volume 8, Issue 2, June 2016

CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization

Henrik A. Friberg

aiming to challenge commercial and open source solvers on mainstream cone support. In this paper, 121 mixed-integer and continuous second-order cone problem instances have been selected from 11 categories as representative for the instances available online. Since current file formats were found incapable, we embrace the new Conic Benchmark Format as standard for conic optimization. Tools are provided to aid integration of this format with other software packages.

Full Text: PDF



Mathematical Programming Computation, Volume 8, Issue 2, June 2016

Erratum to: CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization

Henrik A. Friberg

The below statement was inadvertently missed out during the typesetting process. The correct text is provided below.
In Sect. 4.1, the list of certificates a solver could return for conic continuous optimization problems is not complete as claimed, as the paper was published without the following fifth point:
  • certified dual facial reducibility when we are given a feasible point to problem (P), modified such that b and B are fixed to zero, with a zero-valued objective value, cTc+<C,X>=0 (within a tolerance), and non-zero entries of any self-dual cone. This is a facial reduction certificate for (D) showing it to be ill-posed in the sense of Renegar [2].
This certificate is needed when the problem (P) has an unattained optimal solution or if the objective value can be improved indefinitely even though it has no improving ray (i.e., no certificate of dual infeasibility exists). Both cases are shown to occur in [1] where an algorithm is furthermore constructed with the property of always returning one of the five certificates. This shows the corrected list of certificates to be complete.

References

  1. Permenter, F., Friberg, H.A., Andersen, E.D.: Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach. Technical report. http://www.optimization-online.org/DB_HTML/2015/09/5104.html (2015)
  2. Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5(3), 506–524 (1995)

Full Text: PDF



Mathematical Programming Computation, Volume 8, Issue 2, June 2016

The L-shape search method for triobjective integer programming

Natashia Boland, Hadi Charkhgard, Martin Savelsbergh

We present a new criterion space search method, the L-shape search method, for finding all nondominated points of a triobjective integer program. The method is easy to implement, and is more efficient than existing methods. Moreover, it is intrinsically well-suited for producing high quality approximate nondominated frontiers early in the search process. An extensive computational study demonstrates its efficacy.

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).