MPC

MPC 2016, ISSUE 4



Mathematical Programming Computation, Volume 8, Issue 4, November 2016

Customizing the solution process of COIN-OR’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 mixed-integer 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 COIN-OR’s open-source 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 mixed-integer linear programs using the CBC and CGL COIN-OR packages by cod- ing branch-and-cut strategies and cut generators in Python. The Cython programming language ensures communication between Python and C++ libraries and activates user-defined 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 COIN-OR and is available under open-source 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 branch-and-cut node selection in the solution of a mixed-integer 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 data-flow 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 ADOL-C, a widely-used 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 state-of-the-art 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 open-source software and it will be included in a future release of ADOL-C.

Full Text: PDF



Mathematical Programming Computation, Volume 8, Issue 4, November 2016

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

Dennis Janka, Christian Kirches, Sebastian Sager, Andreas Wa?chter

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. 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 line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton 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 block-BFGS quasi-Newton 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 Schur-complement factorization that is carried out by the active-set 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 node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints

Markus Sinnl, Ivana Ljubic

The Steiner tree problem with revenues, budget and hop-constraints (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 hop-limit 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 hop-constrained 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 hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large- scale instances and/or instances with large hop-limits, for which the size of arc-based 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 branch-and-cut 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 hop-limit 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 large-scale 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 state-of-the-art 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 best-known 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 state-of-the-art 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 (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), 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 speed-up 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

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

Evrim Dalkiran, Hanif D. Sherali

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, 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 RLT-POS.

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



MPC 2016, ISSUE 1



Mathematical Programming Computation, Volume 8, Issue 1, March 2016

A new novel local search integer-programming-based heuristic for PCB assembly on collect-and-place machines

Anupam Seth, Diego Klabjan, Placid M.A new novel local search integer-progr Ferreira

This paper presents the development of a novel vehicle-routing-based algorithm for optimizing component pick-up and placement on a collect-and-place type machine in printed circuit board manufacturing. We present a two-phase 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

Large-scale optimization with the primal-dual column generation method

Jacek Gondzio, Pablo González-Brevis, Pedro Munari

The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered 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 large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage 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 large-scale 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 public-domain 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 branch-and-cut 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 branch-and-cut 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.
© 2008-2020 by Zuse Institute Berlin (ZIB).