MPC 2016, ISSUE 4
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
Customizing the solution process of COINOR’s linear solvers with Python
Mehdi Towhidi, Dominique Orban
Implementations of the simplex method differ mostly in specific aspects such as the pivot rule. Similarly, most relaxation methods for mixedinteger program ming differ mostly in the type of cuts and the exploration of the search tree. We provide a scripting mechanism to easily implement and experiment with primal and dual pivot rules for the simplex method, by building upon COINOR’s opensource linear programming package CLP, without explicitly interacting with the underlying C++ layers of CLP. In the same manner, users can customize the solution process of mixedinteger linear programs using the CBC and CGL COINOR packages by cod ing branchandcut strategies and cut generators in Python. The Cython programming language ensures communication between Python and C++ libraries and activates userdefined customizations as callbacks. Our goal is to emphasize the ease of devel opment in Python while maintaining acceptable performance. The resulting software, named CyLP, has become a part of COINOR and is available under opensource terms. For illustration, we provide an implementation of the positive edge rule—a recently proposed rule that is particularly efficient on degenerate problems—and demonstrate how to customize branchandcut node selection in the solution of a mixedinteger program.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation
Mu Wang, Assefaw Gebremedhin, Alex Pothen
Werevisitanalgorithm[calledEdgePushing(EP)]forcomputingHessians using Automatic Differentiation (AD) recently proposed by Gower and Mello (Optim Methods Softw 27(2): 233–249, 2012). Here we give a new, simpler derivation for the EP algorithm based on the notion of live variables from dataflow analysis in compiler theory and redesign the algorithm with close attention to general applicability and performance. We call this algorithm Livarh and develop an extension of Livarh that incorporates preaccumulation to further reduce execution time—the resulting algo rithm is called Livarhacc. We engineer robust implementations for both algorithms Livarh and Livarhacc within ADOLC, a widelyused operator overloading based AD software tool. Rigorous complexity analyses for the algorithms are provided, and the performance of the algorithms is evaluated using a mesh optimization application and several kinds of synthetic functions as testbeds. The results show that the new algo rithms outperform stateoftheart sparse methods (based on sparsity pattern detection, coloring, compressed matrix evaluation, and recovery) in some cases by orders of mag nitude. We have made our implementation available online as opensource software and it will be included in a future release of ADOLC.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with blockdiagonal Hessian matrix
Dennis Janka, Christian Kirches, Sebastian Sager, Andreas Wächter
We present a quasiNewton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is blockdiagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter linesearch SQP method that computes search directions using an activeset quadratic programming (QP) solver. To take advantage of the blockdiagonal structure of the Hessian matrix, each block is approximated separately by quasiNewton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the blockBFGS quasiNewton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs neces sitate an inertia control mechanism within the sparse Schurcomplement factorization that is carried out by the activeset QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
A nodebased layered graph approach for the Steiner tree problem with revenues, budget and hopconstraints
Markus Sinnl, Ivana Ljubic
The Steiner tree problem with revenues, budget and hopconstraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hoplimit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hopconstrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hopconstraints. Contrary to previous MIP formulations based on layered graphs (that are arcbased models), our model is nodebased. Thus it contains much less variables and allows to tackle large scale instances and/or instances with large hoplimits, for which the size of arcbased layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the under lying MIP formulation. We implemented a branchandcut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hoplimit up to 25.
Full Text: PDF
MPC 2016, ISSUE 3
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
Robert Vanderbei, Kevin Lin, Han Liu, Lie Wang
We propose two approaches to solve largescale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than stateoftheart methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the bestknown sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and stateoftheart methods such as ?1_?s and Mirror Prox regardless of the sparsity level or problem size.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
A nonmonotone GRASP
M. De Santis, P. Festa, G. Liuzzi, S. Lucidi, F. Rinaldi
A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAXCUT), the weighted maximum satisfiability problem (MAXSAT), and the quadratic assignment problem (QAP).
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
Phase retrieval for imaging problems
Fajwel Fogel, Irène Waldspurger, Alexandre D’Aspremont
We study convex relaxation algorithms for phase retrieval on imaging problems. We show that exploiting structural assumptions on the signal and the observations, such as sparsity, smoothness or positivity, can significantly speedup convergence and improve recovery performance. We detail numerical results in molecular imaging experiments simulated using data from the Protein Data Bank.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
RLTPOS: ReformulationLinearization Techniquebased optimization software for solving polynomial programming problems
Evrim Dalkiran, Hanif D. Sherali
In this paper, we introduce a ReformulationLinearization Techniquebased opensource optimization software for solving polynomial programming problems (RLTPOS). We present algorithms and mechanisms that form the backbone of RLTPOS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLTPOS.
Full Text: PDF
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
MPC 2016, ISSUE 1
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
A new novel local search integerprogrammingbased heuristic for PCB assembly on collectandplace machines
Anupam Seth, Diego Klabjan, Placid M. Ferreira
This paper presents the development of a novel vehicleroutingbased algorithm for optimizing component pickup and placement on a collectandplace type machine in printed circuit board manufacturing. We present a twophase heuristic that produces solutions of remarkable quality with respect to other known approaches in a reasonable amount of computational time. In the first phase, a construction procedure is used combining greedy aspects and solutions to subproblems modeled as a generalized traveling salesman problem and quadratic assignment problem. In the second phase, this initial solution is refined through an iterative framework requiring an integer programming step. A detailed description of the heuristic is provided and extensive computational results are presented.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Largescale optimization with the primaldual column generation method
Jacek Gondzio, Pablo GonzálezBrevis, Pedro Munari
The primaldual column generation method (PDCGM) is a generalpurpose column generation technique that relies on the primaldual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and wellcentered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving largescale convex optimization problems. We have selected applications that arise in important reallife contexts such as data analysis (multiple kernel learning problem), decisionmaking under uncertainty (twostage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for largescale optimization problems.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Minimizing the sum of many rational functions
Florian Bugarin, Didier Henrion, Jean Bernard Lasserre
We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be relatively large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how publicdomain software can be used to model and solve such problems. Finally, we also compare with the epigraph approach and the BARON software.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Improving branchandcut performance by random sampling
Matteo Fischetti, Andrea Lodi, Michele Monaci, Domenico Salvagnin, Andrea Tramontani
We discuss the variability in the performance of multiple runs of branchandcut mixed integer linear programming solvers, and we concentrate on the one deriving from the use of different optimal bases of the linear programming relaxations. We propose a new algorithm exploiting more than one of those bases and we show that different versions of the algorithm can be used to stabilize and improve the performance of the solver.
Full Text: PDF
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 20082022 by Zuse Institute Berlin (ZIB).