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 mixedinteger 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 opensource COINOR project.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
CBLIB 2014: a benchmark library for conic mixedinteger and continuous optimization
Henrik A. Friberg
aiming to challenge commercial and open source solvers on mainstream cone support. In this paper, 121 mixedinteger and continuous secondorder 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 mixedinteger 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 zerovalued objective value,
c^{T}c+<C,X>=0
(within a tolerance), and nonzero entries of any selfdual cone.
This is a facial reduction certificate for (D) showing it to be illposed 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
 Permenter, F., Friberg, H.A., Andersen, E.D.:
Solving conic optimization problems via selfdual embedding and facial reduction: a unified approach.
Technical report. http://www.optimizationonline.org/DB_HTML/2015/09/5104.html (2015)
 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 Lshape search method for triobjective integer programming
Natashia Boland, Hadi Charkhgard, Martin Savelsbergh
We present a new criterion space search method, the Lshape 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 wellsuited 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.
© 20082023 by Zuse Institute Berlin (ZIB).