MPC 2020, ISSUE 1
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
A hybrid quasiNewton projectedgradient method with application to Lasso and basispursuit denoising
Ewout van den Berg
We propose a new algorithm for the optimization of convex functions over a polyhedral set in Rn. The algorithm extends the spectral projectedgradient method with limitedmemory BFGS iterates restricted to the present face whenever possible. We prove convergence of the algorithm under suitable conditions and apply the algorithm to solve the Lasso problem, and consequently, the basispursuit denoise problem through the rootfinding framework proposed by van den Berg and Friedlander (SIAM J Sci Comput 31(2):890–912, 2008). The algorithm is especially well suited to simple domains and could also be used to solve boundconstrained problems as well as problems restricted to the simplex.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
A branchandprice algorithm for capacitated hypergraph vertex separation
Michael Bastubbe, Marco E. Lübbecke
We exactly solve the NPhard combinatorial optimization problem of finding a minimum cardinality vertex separator with k (or arbitrarily many) capacitated shores in a hypergraph. We present an exponential size integer programming formulation which we solve by branchandprice. The pricing problem, an interesting optimization problem on its own, has a decomposable structure that we exploit in preprocessing. We perform an extensive computational study, in particular on hypergraphs coming from the application of rearranging a matrix into singlebordered blockdiagonal form. Our experimental results show that our proposal complements the previous exact approaches in terms of applicability for larger k, and significantly outperforms them in the case k=∞.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
Partial hyperplane activation for generalized intersection cuts
Aleksandr M. Kazachkov, Selvaprabu Nadarajah, Egon Balas, François Margot
The generalized intersection cut paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure called partial hyperplane activation (PHA), introduce a variant of PHA based on a notion of hyperplane tilting, and prove the validity of both algorithms. We propose several implementation strategies and parameter choices for our PHA algorithms and provide supporting theoretical results. We computationally evaluate these ideas in the COINOR framework on MIPLIB instances. Our findings shed light on the the strengths of the PHA approach as well as suggest properties related to strong cuts that can be targeted in the future.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
Exploiting sparsity for the min kpartition problem
Guanglei Wang, Hassan Hijazi
The minimum kpartition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the maxcut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a large number of constraints and variables. In this work, we introduce two more compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop theoretical results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon stateoftheart.
Full Text: PDF
MPC 2019, ISSUE 4
Mathematical Programming Computation, Volume 11, Issue 4, December 2019
A derivativefree Gauss–Newton method
Coralia Cartis, Lindon Roberts
We present DFOGN, a derivativefree version of the Gauss–Newton method for solving nonlinear leastsquares problems.
DFOGN uses
linear interpolation of residual values to build a quadratic model of the
objective, which is then used within a typical derivativefree trustregion framework. We show that DFOGN is globally
convergent and requires at most O(??2) iterations to reach approximate firstorder criticality within tolerance ?.
We provide an implementation of DFOGN and compare it to other stateoftheart derivativefree solvers that use quadratic
interpolation models. We demonstrate numerically that despite using only linear residual models, DFOGN performs
comparably to these methods in terms of objective evaluations. Furthermore, as a result of the simplified interpolation
procedure, DFOGN has superior runtime and scalability. Our implementation of DFOGN is available at
https://github.com/numericalalgorithmsgroup/dfogn
(
https://doi.org/10.5281/zenodo.2629875).
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 4, December 2019
Structuredriven fixandpropagate heuristics for mixed integer programming
Gerald Gamrath, Timo Berthold, Stefan Heinz, Michael Winkler
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 4, December 2019
New exact approaches to row layout problems
Anja Fischer Fischer, Frank Fischer, Philipp Hungerländer
Given a set of departments, a number of rows and pairwise connectivities between these departments, the multirow facility layout problem (MRFLP) looks for a nonoverlapping arrangement of these departments in the rows such that the weighted sum of the centertocenter distances is minimized. As even small instances of the MRFLP are rather challenging, several special cases have been considered in the literature. In this paper we present new mixedinteger linear programming formulations for the (spacefree) multirow facility layout problem with given assignment of the departments to the rows that combine distance and betweenness variables. Using these formulations instances with up to 25 departments can be solved to optimality (within at most 6 h) for the first time. Furthermore, we are able to reduce the running times for instances with up to 23 departments significantly in comparison to the literature. Later on we use these formulations in an enumeration scheme for solving the (spacefree) multirow facility layout problem. In particular, we test all possible row assignments, where some assignments are excluded due to our new combinatorial investigations. For the first time this approach enables us to solve instances with two rows with up to 16 departments, with three rows with up to 15 departments and with four and five rows with up to 13 departments exactly in reasonable time.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 4, December 2019
An active set algorithm for robust combinatorial optimization based on separation oracles
Christoph Buchheim, Marianna De Santis
We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a secondoder cone program (SOCP) with integrality constraints. We propose a branchandbound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the Lagrangian dual of the continuous relaxation, where the feasible set of the combinatorial problem is supposed to be given by a separation oracle. The method benefits from the closed form solution of the active set subproblems and from a smart update of pseudoinverse matrices. We present numerical experiments on randomly generated instances and on instances from different combinatorial problems, including the shortest path and the traveling salesman problem, showing that our new algorithm consistently outperforms the stateofthe art mixedinteger SOCP solver of Gurobi.
Full Text: PDF
MPC 2019, ISSUE 3
Mathematical Programming Computation, Volume 11, Issue 3, September 2019
Certifiably optimal sparse principal component analysis
Lauren Berk, Dimitris Bertsimas
This paper addresses the sparse principal component analysis (SPCA) problem for covariance matrices in dimension n aiming to find solutions with sparsity k usingmixed integer optimization. We propose a tailored branchandbound algorithm, OptimalSPCA, that enables us to solve SPCA to certifiable optimality in seconds for n = 100 s, k = 10 s. This same algorithm can be applied to problems with n = 10,000 s or higher to find highquality feasible solutions in seconds while taking several hours to prove optimality. We apply our methods to a number of real data sets to demonstrate that our approach scales to the same problem sizes attempted by other methods, while providing superior solutions compared to those methods, explaining a higher portion of variance and permitting complete control over the desired sparsity. The software that was reviewed as part of this submission has been given the DOI (digital object identifier)
https://doi.org/10.5281/zenodo.2027898
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 3, September 2019
Solving quadratic programs to high precision using scaled iterative refinement
Tobias Weber, Ambros Gleixner, Sebastian Sager
Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floatingpoint operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floatingpoint QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 3, September 2019
Solving equilibrium problems using extended mathematical programming
Youngdae Kim, Michael C. Ferris
We introduce an extended mathematical programming framework for specifying equilibrium problems and their variational representations, such as generalized Nash equilibrium,multiple optimization problemswith equilibrium constraints, and (quasi) variational inequalities, and computing solutions of them from modeling languages. We define a new set of constructs with which users annotate variables and equations of the model to describe equilibrium and variational problems. Our constructs enable a natural translation of the model from one formulation to another more computationally tractable form without requiring the modeler to supply derivatives. In the context of many independent agents in the equilibrium, we facilitate expression of sophisticated structures such as shared constraints and additional constraints on their solutions.We define shared variables and demonstrate their uses for sparse reformulation, economic equilibrium problems sharing economic states, mixed pricing behavior of agents, and so on. We give some equilibrium and variational examples from the literature and describe how to formulate them using our framework. Experimental results comparing performance of various complementarity formulations for shared variables are provided. Our framework has been implemented and is available within GAMS/EMP.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 3, September 2019
SieveSDP: a simple facial reduction algorithm to preprocess semidefinite programs
Yuzixuan Zhu, Gábor Pataki, Quoc TranDinh
We introduce SieveSDP, a simple facial reduction algorithm to preprocess semidefinite programs (SDPs). SieveSDP inspects the constraints of the problem to detect lack of strict feasibility, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on several problem collections from the literature, with many SDPs coming from polynomial optimization.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 3, September 2019
OAR Lib: an open source arc routing library
Oliver Lum, Bruce Golden, Edward Wasil
We present an open source, arc routing Java library that has a flexible graph architecture with solvers for several uncapacitated arc routing problems and the ability to dynamically generate and visualize realworld street networks. The library is hosted at https://github.com/Olibear/ArcRoutingLibrary ( https://doi.org/10.5281/zenodo.2561406). We describe the algorithms in the library, report computational performance, and discuss implementation issues.
Full Text: PDF
MPC 2019, ISSUE 2
Mathematical Programming Computation, Volume 11, Issue 2, June 2019
The (not so) trivial lifting in two dimensions
Ricardo Fukasawa, Laurent Poirrier, Alinson S. Xavier
When generating cuttingplanes for mixedinteger programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the nonbasic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral nonbasic variables using the socalled trivial lifting procedure. Although of polynomialtime complexity in theory, this lifting procedure can be computationally costly in practice. For the case of tworow relaxations, we present a practical algorithm that computes trivial lifting coefficients in constant time, for arbitrary maximal latticefree sets. Computational experiments confirm that the algorithm works well in practice.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 2, June 2019
QPLIB: a library of quadratic programming instances
Fabio Furini, Emiliano Traversi, Pietro Belotti, Antonio Frangioni, Ambros Gleixner, Nick Gould, Leo Liberti, Andrea Lodi, Ruth Misener, Hans Mittelmann, Nikolaos V. Sahinidis, Stefan Vigerske, Angelika Wiegele
This paper describes a new instance library for quadratic programming (QP), i.e., the family of continuous and (mixed)integer optimization problems where the objective function and/or the constraints are quadratic. QP is a very diverse class of problems, comprising subclasses ranging from trivial to undecidable. This diversity is reflected in the variety of QP solution methods, ranging from entirely combinatorial approaches to completely continuous algorithms, including many methods for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the different, interested communities is therefore important. We propose a simple taxonomy for QP instances leading to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 2, June 2019
Solving linear programs with complementarity constraints using branchandcut
Bin Yu, John E. Mitchel, JongShi Pang
A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The presence of the complementarity constraints results in a nonconvex optimization problem. We develop a branchandcut algorithm to find a global optimum for this class of optimization problems, where we branch directly on complementarities. We develop branching rules and feasibility recovery procedures and demonstrate their computational effectiveness in a comparison with CPLEX. The implementation builds on CPLEX through the use of callback routines. The computational results show that our approach is a strong alternative to constructing an integer programming formulation using bigM terms to represent bounds for variables, with testing conducted on general LPCCs as well as on instances generated from bilevel programs with convex quadratic lower level problems.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 2, June 2019
Simplex QPbased methods for minimizing a conic quadratic objective over polyhedra
Alper Atamtürk, Andres Gomez
We consider minimizing a conic quadratic objective over a polyhedron. Such problems arise in parametric valueatrisk minimization, portfolio optimization, and robust optimization with ellipsoidal objective uncertainty; and they can be solved by polynomial interior point algorithms for conic quadratic optimization. However, interior point algorithms are not wellsuited for branchandbound algorithms for the discrete counterparts of these problems due to the lack of effective warm starts necessary for the efficient solution of convex relaxations repeatedly at the nodes of the search tree. In order to overcome this shortcoming, we reformulate the problem using the perspective of the quadratic function. The perspective reformulation lends itself to simple coordinate descent and bisection algorithms utilizing the simplex method for quadratic programming, which makes the solution methods amenable to warm starts and suitable for branchandbound algorithms. We test the simplexbased quadratic programming algorithms to solve convex as well as discrete instances and compare them with the stateoftheart approaches. The computational experiments indicate that the proposed algorithms scale much better than interior point algorithms and return higher precision solutions. In our experiments, for large convex instances, they provide up to 22x speedup. For smaller discrete instances, the speedup is about 13x over a barrierbased branchandbound algorithm and 6x over the LPbased branchandbound algorithm with extended formulations. The software that was reviewed as part of this submission was given the Digital Object identifier https://doi.org/10.5281/zenodo.1489153.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 2, June 2019
Optimizing over pure stationary equilibria in consensus stopping games
Amin Dehghanian, Murat Kurt, Andrew J. Schaefer
Consensus decisionmaking, a widely utilized group decisionmaking process, requires the consent of all participants. We consider consensus stopping games, a class of stochastic games arising in the context of consensus decisionmaking that require the consent of all players to terminate the game. We show that a consensus stopping game may have many pure stationary equilibria, which in turn raises the question of equilibrium selection. Given an objective criterion, we study the NPhard problem of finding a best pure stationary equilibrium. We characterize the pure stationary equilibria, show that they form an independence system, and develop several families of valid inequalities. We then solve the equilibrium selection problem as a mixedinteger linear program by a branchandcut approach. Our computational results demonstrate the effectiveness of our approach over a commercial solver.
Full Text: PDF
MPC 2019, ISSUE 1
Mathematical Programming Computation, Volume 11, Issue 1, March 2019
CasADi: a software framework for nonlinear optimization and optimal control
Joel A. E. Andersson, Joris Gillis, Greg Horn, James B. Rawlings, Moritz Diehl
We present CasADi, an opensource software framework for numerical optimization. CasADi is a generalpurpose tool that can be used to model and solve optimization problems with a large degree of flexibility, larger than what is associated with popular algebraic modeling languages such as AMPL, GAMS, JuMP or Pyomo. Of special interest are problems constrained by differential equations, i.e. optimal control problems. CasADi is written in selfcontained C++, but is most conveniently used via fullfeatured interfaces to Python, MATLAB or Octave. Since its inception in late 2009, it has been used successfully for academic teaching as well as in applications from multiple fields, including process control, robotics and aerospace. This article gives an uptodate and accessible introduction to the CasADi framework, which has undergone numerous design improvements over the last 7 years.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 1, March 2019
A computational comparison of symmetry handling methods for mixed integer programs
Marc E. Pfetsch, Thomas Rehn
The handling of symmetries in mixed integer programs in order to speed up the solution process of branchandcut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present in the MIPLIB 2010 instances. It turns out that many instances are affected by symmetry and most symmetry groups contain full symmetric groups as factors. We then present (variants of) six symmetry handling methods from the literature. Their implementation is tested on several testsets. On very symmetric instances used previously in the literature, it is essential to use methods like isomorphism pruning, orbital fixing, or orbital branching. Moreover, tests on the MIPLIB instances show that isomorphism pruning, orbital fixing, or adding symmetry breaking inequalities allow to speedup the solution process by about 15% and more instances can be solved within the time limit.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 1, March 2019
Computing feasible points for binary MINLPs with MPECs
Lars Schewe, Martin Schmidt
Nonconvex mixedbinary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixedbinary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 1, March 2019
New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
Hezhi Luo, Xiaodi Bai, Gino Lim, Jiming Peng
We consider a quadratic program with a few negative eigenvalues (QPrNE) subject to linear and convex quadratic constraints that covers many applications and is known to be NPhard even with one negative eigenvalue (QP1NE). In this paper, we first introduce a new global algorithm (ADMBB), which integrates several simple optimization techniques such as alternative direction method, and branchandbound, to find a globally optimal solution to the underlying QP within a prespecified ϵtolerance. We establish the convergence of the ADMBB algorithm and estimate its complexity. Second, we develop a global search algorithm (GSA) for QP1NE that can locate an optimal solution to QP1NE within ϵtolerance and estimate the worstcase complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to largescale QPrNE instances when r≤10, and the GSA outperforms the ADMBB for most of the tested QP1NE instances. The software reviewed as part of this submission was given the DOI (digital object identifier)
https://doi.org/10.5281/zenodo.1344739.
Full Text: PDF
Mathematical Programming Computation, Volume 11, Issue 1, March 2019
Enumeration of 2level polytopes
Adam Bohn, Yuri Faenza, Samuel Fiorini, Vissarion Fisikopoulos, Marco Macchia, Kanstantsin Pashkovich
A (convex) polytope P is said to be 2level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of 2level polytopes of a given dimension d, and provide complete experimental results for d⩽7. Our approach is inductive: for each fixed (d−1)dimensional 2level polytope P_{0}, we enumerate all ddimensional 2level polytopes P that have P_{0} as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet P_{0}, we obtain all 2level polytopes in dimension d.
Full Text: PDF
MPC 2018, ISSUE 4
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Cubic regularization in symmetric rank1 quasiNewton methods
Hande Y. Benson, David F. Shanno
QuasiNewton methods based on the symmetric rankone (SR1) update have been known to be fast and provide better approximations of the true Hessian than popular ranktwo approaches, but these properties are guaranteed under certain conditions which frequently do not hold. Additionally, SR1 is plagued by the lack of guarantee of positive definiteness for the Hessian estimate. In this paper, we propose cubic regularization as a remedy to relax the conditions on the proofs of convergence for both speed and accuracy and to provide a positive definite approximation at each step. We show that the nstep convergence property for strictly convex quadratic programs is retained by the proposed approach. Extensive numerical results on unconstrained problems from the CUTEr test set are provided to demonstrate the computational efficiency and robustness of the approach.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
Daniel Juhl, David M. Warme, Pawel Winter, Martin Zachariasen
The GeoSteiner software package has for about 20 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach—allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. We describe these (previously unpublished) enhancements, and present a new computational study wherein we run the current code on the largest problem instances from the 2000study, and on a number of larger problem instances. The computational study is performed using the commercial GeoSteiner 4.0 code base, and the performance is compared to the publicly available GeoSteiner 3.1 code base as well as the code base from the 2000study. The software studied in the paper is being released as GeoSteiner 5.0 under an open source license.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
A generalized alternating direction method of multipliers with semiproximal terms for convex composite conic programming
Yunhai Xiao, Liang Chen, Donghui Li
In this paper, we propose a generalized alternating direction method of multipliers (ADMM) with semiproximal terms for solving a class of convex composite conic optimization problems, of which some are highdimensional, to moderate accuracy. Our primary motivation is that this method, together with properly chosen semiproximal terms, such as those generated by the recent advance of block symmetric Gauss–Seidel technique, is capable of tackling these problems. Moreover, the proposed method, which relaxes both the primal and the dual variables in a natural way with a common relaxation factor in the interval of (0, 2), has the potential of enhancing the performance of the classic ADMM. Extensive numerical experiments on various doubly nonnegative semidefinite programming problems, with or without inequality constraints, are conducted. The corresponding results showed that all these multiblock problems can be successively solved, and the advantage of using the relaxation step is apparent.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Matrix minor reformulation and SOCPbased spatial branchandcut method for the AC optimal power flow problem
Burak Kocuk, Santanu S. Dey, X. Andy Sun
Alternating current optimal power flow (AC OPF) is one of the most fundamental optimization problems in electrical power systems. It can be formulated as a semidefinite program (SDP) with rank constraints. Solving AC OPF, that is, obtaining near optimal primal solutions as well as high quality dual bounds for this nonconvex program, presents a major computational challenge to today’s power industry for the realtime operation of largescale power grids. In this paper, we propose a new technique for reformulation of the rank constraints using both principal and nonprincipal 2by2 minors of the involved Hermitian matrix variable and characterize all such minors into three types. We show the equivalence of these minor constraints to the physical constraints of voltage angle differences summing to zero over three and fourcycles in the power network. We study secondorder conic programming (SOCP) relaxations of this minor reformulation and propose strong cutting planes, convex envelopes, and bound tightening techniques to strengthen the resulting SOCP relaxations. We then propose an SOCPbased spatial branchandcut method to obtain the global optimum of AC OPF. Extensive computational experiments show that the proposed algorithm significantly outperforms the stateoftheart SDPbased OPF solver and on a simple personal computer is able to obtain on average a 0.71% optimality gap in no more than 720 s for the most challenging power system instances in the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
RBFOpt: an opensource library for blackbox optimization with costly function evaluations
Alberto Costa, Giacomo Nannicini
We consider the problem of optimizing an unknown function given as an oracle over a mixedinteger boxconstrained set. We assume that the oracle is expensive to evaluate, so that estimating partial derivatives by finite differences is impractical. In the literature, this is typically called a blackbox optimization problem with costly evaluation. This paper describes the solution methodology implemented in the opensource library RBFOpt, available on COINOR. The algorithm is based on the Radial Basis Function method originally proposed by Gutmann (J Glob Optim 19:201–227, 2001. https://doi.org/10.1023/A:1011255519438), which builds and iteratively refines a surrogate model of the unknown objective function. The two main methodological contributions of this paper are an approach to exploit a noisy but less expensive oracle to accelerate convergence to the optimum of the exact oracle, and the introduction of an automatic model selection phase during the optimization process. Numerical experiments show that RBFOpt is highly competitive on a test set of continuous and mixedinteger nonlinear unconstrained problems taken from the literature: it outperforms the opensource solvers included in our comparison by a large amount, and performs slightly better than a commercial solver. Our empirical evaluation provides insight on which parameterizations of the algorithm are the most effective in practice. The software reviewed as part of this submission was given the Digital Object Identifier (DOI)
https://doi.org/10.5281/zenodo.597767.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
ADMM for the SDP relaxation of the QAP
Danilo Elias Oliveira, Henry Wolkowicz, Yangyang Xu
Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NPhard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Learning customized and optimized lists of rules with mathematical programming
Cynthia Rudin, Seyda Ertekin
We introduce a mathematical programming approach to building rule lists, which are a type of interpretable, nonlinear, and logical machine learning classifier involving IFTHEN rules. Unlike traditional decision tree algorithms like CART and C5.0, this method does not use greedy splitting and pruning. Instead, it aims to fully optimize a combination of accuracy and sparsity, obeying userdefined constraints. This method is useful for producing nonblackbox predictive models, and has the benefit of a clear userdefined tradeoff between training accuracy and sparsity. The flexible framework of mathematical programming allows users to create customized models with a provable guarantee of optimality. The software reviewed as part of this submission was given the DOI (Digital Object Identifier)
https://doi.org/10.5281/zenodo.1344142.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
QSDPNAL: a twophase augmented Lagrangian method for convex quadratic semidefinite programming
Xudong Li, Defeng Sun, KimChuan Toh
In this paper, we present a twophase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNALPhase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNALPhase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our twophase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier)
https://doi.org/10.5281/zenodo.1206980.
Full Text: PDF
MPC 2018, ISSUE 3
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Asynchronously parallel optimization solver for finding multiple minima
Jeffrey Larson, Stefan M. Wild
We propose and analyze an asynchronously parallel optimization algorithmfor finding multiple, highquality minima of nonlinear optimization problems. Ourmultistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that when there are finitely many minima, the algorithm almost surely starts a finite number of local optimization runs and identifies every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a Python implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability is shown to scale well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to perform the function evaluation is highly variable. An implementation of the algorithm is available in the libEnsemble library at https://github.com/Libensemble/libensemble.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
Pierre Bonami, Oktay Günlük, Jeff Linderoth
We present effective linear programming based computational techniquesfor solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the oddcycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branchandcut framework, together with a common integralitybased preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a wellknown family of test instances. Our linear programming based solver is competitive with SDPbased state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
A hybrid LP/NLP paradigm for global optimization relaxations
Aida Khajavirad, Nikolaos V. Sahinidis
Polyhedral relaxations have been incorporated in a variety of solvers for theglobal optimization of mixedinteger nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with failsafe techniques, convexity identification at each node of the branchandbound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widelyused test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Intersection cuts for single row corner relaxations
Ricardo Fukasawa, Laurent Poirrier, Álinson S. Xavier
We consider the problem of generating inequalities that are valid for onerow relaxations of a simplex tableau, with the integrality constraints preserved for one or more nonbasic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixedinteger problems. We first consider the case of a single nonbasic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained tworow model, and prove that all its facets arise from a finite number of maximal (Z × Z + )free splits and wedges. The resulting cuts generalize both MIR and 2step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (Z × Z + )free sets corresponding to facetdefining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the socalled trivial fillin function to exploit the integrality of more nonbasic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.
Full Text: PDF
MPC 2018, ISSUE 2
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
Detecting almost symmetries of graphs
Ben Knueven, Jim Ostrowski, Sebastian Pokutta
We present a branchandbound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that minimizes the number of vertex orbits. We call the symmetries on such a subgraph “almost symmetries” of G. We implement our branchandbound framework in PEBBL to allow for parallel enumeration and demonstrate good scaling up to 16 cores. We show that the presented branching strategy is much better than a random branching strategy on the tested graphs. Finally, we consider the presented strategy as a heuristic for quickly finding almost symmetries of a graph G. The software that was reviewed as part of this submission has been issued the Digital Object Identifier
DOI:10.5281/zenodo.840558.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
pyomo.dae: a modeling and automatic discretization framework for optimization with differential and algebraic equations
Bethany Nicholson, John D. Siirola, JeanPaul Watson, Victor M. Zavala, Lorenz T. Biegler
We describe pyomo.dae, an open source Pythonbased modeling framework that enables highlevel abstract specification of optimization problems with differential and algebraic equations. The pyomo.dae framework is integrated with the Pyomo open source algebraic modeling language, and is available at http://www. pyomo.org. One key feature of pyomo.dae is that it does not restrict users to stan dard, predefined forms of differential equations, providing a high degree of modeling flexibility and the ability to express constraints that cannot be easily specified in other modeling frameworks. Other key features of pyomo.dae are the ability to specify optimization problems with highorder differential equations and partial differential equations, defined on restricted domain types, and the ability to automatically trans form highlevel abstract models into finitedimensional algebraic problems that can be solved with offtheshelf solvers. Moreover, pyomo.dae users can leverage existing capabilities of Pyomo to embed differential equation models within stochastic and integer programming models and mathematical programs with equilibrium constraint formulations. Collectively, these features enable the exploration of new modeling con cepts, discretization schemes, and the benchmarking of stateoftheart optimization solvers.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
Algorithmic innovations and software for the dual decomposition method applied to stochastic mixedinteger programs
Kibaek Kim, Victor M. Zavala
We present algorithmic innovations for the dual decomposition method to address twostage stochastic programs with mixedinteger recourse and provide an opensource software implementation that we call DSP. Our innovations include the incorporation of Benderslike cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible firststage solutions for problems without (relative) complete recourse. We also use an interiorpoint cutting plane method with new termination criteria for solving the Lagrangian master problem. We prove that the algorithm converges to an optimal solution of the Lagrangian dual problem in a finite number of iterations, and we also prove that convergence can be achieved even if the master problem is solved suboptimally. DSP can solve instances specified in C code, SMPS files, and Julia script. DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradi ent dual updates that we use to perform benchmarks. We present extensive numerical results using SIPLIB instances and a large unit commitment problem to demonstrate that the proposed innovations provide significant improvements in the number of iter ations and solution times. The software reviewed as part of this submission has been given the Digital Object Identifier (DOI)
https://doi.org/10.5281/zenodo.998971.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
mplrs: A scalable parallel vertex/facet enumeration code
David Avis, Charles Jordan
We describe a new parallel implementation, mplrs, of the vertex enumer ation code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C++ which runs on a shared memory machine. By improving load balancing we are able to greatly improve performance for medium to large scale parallelization of lrs. We report computational results comparing parallel and sequential codes for vertex/facet enu meration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested. The software that was reviewed as part of this submission is included in lrslib062.tar.gz which has MD5 hash be5da7b3b90cc2be628dcade90c5d 1b9.
Full Text: PDF
MPC 2018, ISSUE 1
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
SparseBSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
Tillmann Weisser, Jean B. Lasserre, KimChuan Toh
We provide a sparse version of the bounded degree SOS hierarchy BSOS (Lasserre et al. in EURO J Comp Optim:87–117, 2017) for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this SparseBSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem.Moreover, for the class of SOSconvex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Branchandcut for linear programs with overlapping SOS1 constraints
Tobias Fischer, Marc E. Pfetsch
SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branchandcut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, preprocessing, primal heuristics, and cutting planes. In an extensive computational study, we evaluate the components of our implementation on instances for three different applications. We also demonstrate the effectiveness of this approach by comparing it to the solution of a mixedinteger programming formulation, if the variables appearing in SOS1 constraints arbounded.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
A robust and scalable algorithm for the Steiner problem in graphs
Thomas Pajor, Eduardo Uchoa, Renato F. Werneck
We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recentlyproposed fast local searches. We also propose a fast implementation of a wellknown dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branchandbound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Parallelizing the dual revised simplex method
Q. Huangfu, J. A. J. Hall
This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational results show that the performance of PAMI is superior to that of the leading opensource simplex solver, and that SIP complements PAMI in achieving speedup when PAMI results in slowdown. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and this paper presents computational results demonstrating their value. In developing the first parallel revised simplex solver of general utility, this work represents a significant achievement in computational optimization.
Full Text: PDF
MPC 2017, ISSUE 4
Mathematical Programming Computation, Volume 9, Issue 4, December 2017
A branchandbound algorithm for instrumental variable quantile regression
Guanglin Xu, Samuel Burer
This paper studies a statistical problem called instrumental variable quantile regression (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NPhard—we develop a branchandbound algorithm to solve it globally. We also derive bounds on key variables in the problem, which are valid asymptotically for increasing sample size. We compare our method with two well known global solvers, one of which requires the computed bounds. On random instances, our algorithm performs well in terms of both speed and robustness.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 4, December 2017
Liftandproject cuts for convex mixed integer nonlinear programs
Mustafa R. Kilinc, Jeff Linderoth, James Luedtke
We describe a computationally effective method for generating liftandproject cuts for convex mixedinteger nonlinear programs (MINLPs). The method relies on solving a sequence of cutgenerating linear programs and in the limit generates an inequality as strong as the liftandproject cut that can be obtained from solving a cutgenerating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one liftandproject closure for a variety of convex MINLP instances. The results indicate that liftandproject cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branchandcut solver for convex MINLPs significantly reduces the total solution time for many instances.We also demonstrate that combining liftandproject cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, liftandproject cuts may be as effective for solving convex MINLPs as they have been for solving mixedinteger linear programs.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 4, December 2017
Lifted collocation integrators for direct optimal control in ACADO toolkit
Rien Quirynen, Sebastien Gros, Boris Houska, Moritz Diehl
This paper presents a class of efficient Newtontype algorithms for solving the nonlinear programs (NLPs) arising from applying a direct collocation approach to continuous time optimal control. The idea is based on an implicit lifting technique including a condensing and expansion step, such that the structure of each subproblem corresponds to that of themultiple shooting method for direct optimal control.We establish the mathematical equivalence between the Newton iteration based on direct collocation and the proposed approach, and we discuss the computational advantages of a lifted collocation integrator. In addition, we investigate different inexact versions of the proposed scheme and study their convergence and computational properties. The presented algorithms are implemented as part of the opensource ACADO code generation software for embedded optimization. Their performance is illustrated on a benchmark case study of the optimal control for a chain of masses. Based on these results, the use of lifted collocationwithin direct multiple shooting allows for a computational speedup factor of about 10 compared to a standard collocation integrator and a factor in the range of 10–50 compared to direct collocation using a generalpurpose sparse NLP solver.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 4, December 2017
On the computational efficiency of subgradient methods: a case study with Lagrangian bounds
Antonio Frangioni, Bernard Gendron, Enrico Gorgone
Subgradient methods (SM) have long been the preferred way to solve the largescale Nondifferentiable Optimization problems arising from the solution of Lagrangian Duals (LD) of Integer Programs (IP). Although other methods can have better convergence rate in practice, SM have certain advantages that may make them competitive under the right conditions. Furthermore, SMhave significantly progressed in recent years, and new versions have been proposed with better theoretical and practical performances in some applications.We computationally evaluate a large class of SM in order to assess if these improvements carry over to the IP setting. For this we build a unified scheme that covers many of the SMproposed in the literature, comprised some often overlooked features like projection and dynamic generation of variables. We finetune the many algorithmic parameters of the resulting large class of SM, and we test them on two different LDs of the FixedCharge Multicommodity Capacitated Network Design problem, in order to assess the impact of the characteristics of the problem on the optimal algorithmic choices. Our results show that, if extensive tuning is performed, SM can be competitive with more sophisticated approaches when the tolerance required for solution is not too tight, which is the case when solving LDs of IPs.
Full Text: PDF
MPC 2017, ISSUE 3
Mathematical Programming Computation, Volume 9, Issue 3, September 2017
Convex quadratic relaxations for mixedinteger nonlinear programs in power systems
Hassan Hijazi, Carleton Coffrin, Pascal Van Hentenryck
This paper presents a set of new convex quadratic relaxations for nonlinear and mixedinteger nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to stateoftheart semidefinite programming relaxations. Three case studies in optimal power flow, optimal transmission switching and capacitor placement demonstrate the benefits of the new relaxations.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 3, September 2017
Extended formulations in mixed integer conic quadratic programming
Juan Pablo Vielma, Iain Dunning, Joey Huchette, Miles Lubin
In this paper we consider the use of extended formulations in LPbased algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by BenTal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulationbased algorithms forMICQP.We find that this new formulation can be used to improve various LPbased algorithms. In particular, the formulation provides an easytoimplement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 3, September 2017
New computerbased search strategies for extreme functions of the Gomory–Johnson infinite group problem
Matthias Köppe, Yuan Zhou
We describe new computerbased search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions.
Full Text: PDF
MPC 2017, ISSUE 2
Mathematical Programming Computation, Volume 9, Issue 2, June 2017
Dijkstra meets Steiner: a fast exact goaloriented Steiner tree algorithm
Stefan Hougardy, Jannik Silvanus, Jens Vygen
We present a new exact algorithm for the Steiner tree problem in edgeweighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a wellknown concept to speed up shortest path computations. Our algorithm matches the best known worstcase run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the ddimensional rectilinear Steiner tree problem for d?{3,4,5}d?{3,4,5}, whose Hanan grids contain up to several millions of edges.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 2, June 2017
Thinning out Steiner trees: a nodebased model for uniform edge costs
Matteo Fischetti, Markus Leitner, Ivana Ljubic, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin, Markus Sinnl
The Steiner tree problem is a challenging NPhard problem. Many hard instances of this problem are publicly available, that are still unsolved by stateoftheart branchandcut codes. A typical strategy to attack these instances is to enrich the polyhedral description of the problem, and/or to implement more and more sophisticated separation procedures and branching strategies. In this paper we investigate the opposite viewpoint, and try to make the solution method as simple as possible while working on the modeling side. Our working hypothesis is that the extreme hardness of some classes of instances mainly comes from overmodeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. In our computational study, we first show that this new model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. Moreover, we report improved solutions for several SteinLib instances, including the (in)famous hypercube ones. We also demonstrate how to build a unified solver on top of the new nodebased model and the previous stateoftheart model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually. The presented solver is the winner of the DIMACS Challenge on Steiner trees in most of the considered categories.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 2, June 2017
SCIPJack—a solver for STP and variants with parallelization extensions
Gerald Gamrath, Thorsten Koch, Stephen J. Maher, Daniel Rehfeldt, Yuji Shinano
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problemspecific. In contrast, this paper introduces a generalpurpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a stateoftheart MIPframework. The result is a highperformance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 2, June 2017
Swapvertex based neighborhood for Steiner tree problems
ZhangHua Fu, JinKao Hao
Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swapvertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swapvertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swapvertex moves. Additionally, in order to discriminate different swapvertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swapvertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.
Full Text: PDF
MPC 2017, ISSUE 1
Mathematical Programming Computation, Volume 9, Issue 1, March 2017
Computing convex hulls and counting integer points with polymake
Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, Thomas Rehn
The main purpose of this paper is to report on the state of the art of computing integer hulls and their facets as well as counting lattice points in convex polytopes. Using the polymake system we explore various algorithms and implementations. Our experience in this area is summarized in ten “rules of thumb”.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 1, March 2017
Fast separation for the threeindex assignment problem
Trivikram Dokka, Ioannis Mourtos, Frits C. R. Spieksma
A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x, denoted as supp(x), which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of supp(x). Although several wellknown separation algorithms exploit the sparsity of x, we revisit this idea in order to take sparsity explicitly into account in the timecomplexity of separation and also design faster algorithms. We apply this approach to two classes of facetdefining inequalities for the threeindex assignment problem, and obtain separation algorithms whose time complexity is linear in supp(x) instead of n. We indicate that this can be generalized to the axial kindex assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 1, March 2017
Improved branchcutandprice for capacitated vehicle routing
Diego Pecin, Artur Pessoa, Marcus Poggi, Eduardo Uchoa
The best performing exact algorithms for the capacitated vehicle routing problem developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the subset row cuts. This work introduces a technique for greatly reducing the impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed branchcutandprice algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.
Full Text: PDF
Mathematical Programming Computation, Volume 9, Issue 1, March 2017
On efficiently combining limitedmemory and trustregion techniques
Oleg Burdakov, Lujin Gong, Spartak Zikrin, Yaxiang Yuan
Limitedmemory quasiNewton methods and trustregion methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of largescale problems. For this reason, the limitedmemory methods are usually combined with a line search. We show how to efficiently combine limitedmemory and trustregion techniques. One of our approaches is based on the eigenvalue decomposition of the limitedmemory quasiNewton approximation of the Hessian matrix. The decomposition allows for finding a nearlyexact solution to the trustregion subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasiNewton direction in linesearch limitedmemory methods. The other approach is based on two new eigenvaluebased norms. The advantage of the new norms is that the trustregion subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvaluebased limitedmemory trustregion methods are globally convergent. Moreover, we propose improved versions of the existing limitedmemory trustregion algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with linesearch versions of the LBFGS method.
Full Text: PDF
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.A new novel local search integerprogr 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
MPC 2015, ISSUE 4
Mathematical Programming Computation, Volume 7, Issue 4, December 2015
Progress in presolving for mixed integer programming
Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger, Dieter Weninger
This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of realworld supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20% on affected instances while not degrading the performance on the remaining problems.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 4, December 2015
A quasiNewton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees
Xiaocun Que, Frank E. Curtis
A line search algorithm for minimizing nonconvex and/or nonsmooth objective functions is presented. The algorithm is a hybrid between a standard Broyden–Fletcher–Goldfarb–Shanno (BFGS) and an adaptive gradient sampling (GS) method. The BFGS strategy is employed because it typically yields fast convergence to the vicinity of a stationary point, and together with the adaptive GS strategy the algorithm ensures that convergence will continue to such a point. Under suitable assumptions, it is proved that the algorithm converges globally with probability one. The algorithm has been implemented inC++and the results of numerical experiments illustrate the efficacy of the proposed approach.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 4, December 2015
PEBBL: an objectoriented framework for scalable parallel branch and bound
Jonathan Eckstein, William E. Hart, Cynthia A. Phillips
Parallel Enumeration and BranchandBound Library (PEBBL) is a C++ class library implementing the underlying operations needed to support a wide variety of branchandbound algorithms on MPIbased messagepassing distributedmemory parallel computing environments. PEBBL can be customized to support applicationspecific operations, while managing the generic aspects of branch and bound, such as maintaining the active subproblem pool across multiple processors, load balancing, and termination detection. PEBBL is designed to provide highly scalable performance on large numbers of processor cores.We describe the basics of PEBBL’s architecture, with emphasis on the features most critical to is high scalability, including its flexible twolevel load balancing architecture and its support for a synchronously parallel rampup phase.We also present an example application: themaximummonomial agreement problem arising from certain machine learning applications. For sufficiently difficult problem instances, we show essentially linear speedup on over 6000 processor cores, demonstrating a new state of the art in scalability for branchandbound implementations. We also show how processor cache effects can lead to reproducibly superlinear speedups.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 4, December 2015
Computational study of decomposition algorithms for meanrisk stochastic linear programs
Lewis Ntaimo, Tanisha G. Cotton
Meanrisk stochastic programs include a risk measure in the objective to model risk averseness for many problems in science and engineering. This paper reports a computational study of meanrisk twostage stochastic linear programs with recourse based on absolute semideviation (ASD) and quantile deviation (QDEV). The studywas aimed at performing an empirical investigation of decomposition algorithms for stochastic programs with quantile and deviation meanrisk measures; analyzing how the instance solutions vary across different levels of risk; and understanding when it is appropriate to use a given meanrisk measure. Aggregated optimality cut and separate cut subgradientbased algorithms were implemented for each meanrisk model. Both types of algorithms show similar computational performance for ASD whereas the separate cut algorithm outperforms the aggregated cut algorithm for QDEV. The study provides several insights. For example, the results reveal that the riskneutral approach is still appropriate for most of the standard stochastic programming test instances due to their uniform or normallike marginal distributions. However, when the distributions are modified, the riskneutral approach may no longer be appropriate and the riskaverse approach becomes necessary. The results also show that ASD is a more conservative meanrisk measure than QDEV.
Full Text: PDF
MPC 2015, ISSUE 3
Mathematical Programming Computation, Volume 7, Issue 3, September 2015
A note on “On fast trust region methods for quadratic models with linear constraints”, by Michael J.D. Powell
Daniel Bienstock, Philip E. Gill, Nick Gould
The following paper, “On fast trust region methods for quadratic models with linear constraints” by Michael J.D. Powell, was submitted to Mathematical Programming Computation in August 2014, andwas still in review when we became aware of Mike’s deteriorating health. Unfortunately, despite our best efforts and those of two referees, Mike died before we were able to send him our verdict. Both referees had concerns about points that needed further explanation, but in all likelihood—and after a few clarifying iterations—the paper would ultimately have been published. As we believe that the ideas central to the paper are of general interest to the journal’s readership, we have taken the unusual step of publishing the paper “as is”. Readers might, like the referees, question some of the statements made, but we feel it would be wrong tosecond guess Mike’s intentions, and have chosen to leave such statements alone.Mike had a profound effect on computational nonlinear optimization. We dedicate this paper to his memory.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 3, September 2015
On fast trust region methods for quadratic models with linear constraints
M.J. D. Powell
Quadratic models Qk (x), x ? Rn, of the objective function F(x), x ? Rn, are used by many successful iterative
algorithms for minimization, where k is the iteration number. Given the vector of variables xk ? Rn, a new vector xk+1
may be calculated that satisfies Qk (xk+1) < Qk (xk ), in the hope that it provides the reduction F(xk+1) < F(xk ).
Trust region methods include a bound of the form xk+1 ? xk ? k . Also we allow general linear constraints on the
variables that have to hold at xk and at xk+1. We consider the construction of xk+1, using only of magnitude n^{2} operations
on a typical iteration when n is large. The linear constraints are treated by active sets, which may be updated during an
iteration, and which decrease the number of degrees of freedom in the variables temporarily, by restricting x to an affine
subset of Rn. Conjugate gradient and Krylov subspace methods are addressed for adjusting the reduced variables, but the
resultant steps are expressed in terms of the original variables. Termination conditions are given that are intended
to combine suitable reductions in Qk (·) with a sufficiently small number of steps. The reason for our work is that xk+1 is
required in the LINCOA software of the author, which is designed for linearly constrained optimization without derivatives
when there are hundreds of variables. Our studies go beyond the final version of LINCOA, however, which employs conjugate
gradients with termination at the trust region boundary. In particular, we find that, if an active set is updated at a
point that is not the trust region centre, then the Krylov method may terminate too early due to a degeneracy.
An extension to the conjugate gradient method for searching round the trust region boundary receives attention too,
but it was also rejected from LINCOA, because of poor numerical results. The given techniques of LINCOA seem to be
adequate in practice.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 3, September 2015
Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm
Keld Helsgaun
The equality generalized traveling salesman problem (EGTSP) is an extension of the traveling salesman problem (TSP) where the set of cities is partitioned into clusters, and the salesman has to visit every cluster exactly once. It is well known that any instance of EGTSP can be transformed into a standard asymmetric instance of the TSP, and therefore solved with a TSP solver. This paper evaluates the performance of the stateofthe art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed EGTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a wellknown library of benchmark instances, GTSPLIB, could be solved to optimality in a reasonable time. In addition, it was possible to solve a series of new verylargescale instances with up to 17,180 clusters and 85,900 vertices. Optima for these instances are not known but it is conjectured that LKH has been able to find solutions of a very high quality. The program’s performance has also been evaluated on a large number of instances generated by transforming arc routing problem instances into EGTSP instances. The program is free of charge for academic and noncommercial use and can be downloaded in source code.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 3, September 2015
A parallel quadratic programming method for dynamic optimization problems
Janick V. Frasch, Sebastian Sager, Moritz Diehl
Quadratic programming problems (QPs) that arise from dynamic optimization problems typically exhibit a very particular structure. We address the ubiquitous case where these QPs are strictly convex and propose a dual Newton strategy that exploits the blockbandedness similarly to an interiorpoint method. Still, the proposed method features warmstarting capabilities of activeset methods. We give details for an efficient implementation, including tailored numerical linear algebra, step size computation, parallelization, and infeasibility handling. We prove convergence of the algorithm for the considered problem class. A numerical study based on the opensource implementation qpDUNES shows that the algorithm outperforms both wellestablished general purpose QP solvers as well as stateoftheart tailored control QP solvers significantly on the considered benchmark problems.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 3, September 2015
SDPNAL+: a majorized semismooth NewtonCG augmented Lagrangian method for semidefinite programming with nonnegative constraints
KimChuan Toh, Liuqin Yang, Defeng Sun
In this paper, we present a majorized semismooth NewtonCG augmented Lagrangian method, called SDPNAL+, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL+ is a much enhanced version of SDPNAL introduced by Zhao et al. (SIAM J Optim 20:1737–1765, 2010) for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton CG augmented Lagrangian method coupled with a convergent 3block alternating direction method of multipliers introduced recently by Sun et al. (SIAM J Optim, to appear). Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Wen et al. (Math Program Comput 2:203– 230, 2010) and (2) a twoeasyblockdecomposition hybrid proximal extragradient method called 2EBDHPE by Monteiro et al. (Math Program Comput 1–48, 2014). In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of 10?6 efficiently, while SDPAD and 2EBDHPE successfully solve 30 and 16 problems, respectively. In addition, SDPNAL+ appears to be the only viable method currently available to solve large scale SDPs arising from rank1 tensor approximation problems constructed by Nie and Wang (SIAM J Matrix Anal Appl 35:1155–1179, 2014). The largest rank1 tensor approximation problem we solved (in about 14.5 h) is nonsym(21,4), in which its resulting SDP problem has matrix dimension n = 9261 and the number of equality constraints m = 12,326,390.
Full Text: PDF
MPC 2015, ISSUE 2
Mathematical Programming Computation, Volume 7, Issue 2, June 2015
The strength of multirow models
Quentin Louveaux, Laurent Poirrier, Domenico Salvagnin
We develop a method for computing facetdefining valid inequalities for any mixedinteger set PJ . While our practical implementation does not return only facetdefining inequalities, it is able to find a separating cut whenever one exists. The separator is not comparable in speed with the specific cuttingplane generators used in branchandcut solvers, but it is generalpurpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixedinteger problem, even when there exists no specific implementation for computing cuts with PJ . Exploiting this, we evaluate, from a computational perspective, the usefulness of cuts derived from several types of multirow relaxations. In particular, we presentresults with four different strengthenings of the tworow intersection cut model, and multirow models with up to fifteen rows. We conclude that only fullystrengthened tworow cuts seem to offer a significant advantage over tworow intersection cuts. Our results also indicate that the improvement obtained by going frommodelswith very few rows to models with up to fifteen rows may not be worth the increased computing cost.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 2, June 2015
Generalized alternating direction method of multipliers: new theoretical insights and applications
Ethan X. Fang, Bingsheng He, Han Liu, Xiaoming Yuan
Recently, the alternating direction method of multipliers (ADMM) has received intensive attention from a broad spectrum of areas. The generalized ADMM (GADMM) proposed by Eckstein and Bertsekas is an efficient and simple acceleration scheme of ADMM. In this paper, we take a deeper look at the linearized version of GADMM where one of its subproblems is approximated by a linearization strategy. This linearized version is particularly efficient for a number of applications arising from different areas. Theoretically, we show the worstcase O(1/k) convergence rate measured by the iteration complexity (k represents the iteration counter) in both the ergodic and a nonergodic senses for the linearized version of GADMM. Numerically, we demonstrate the efficiency of this linearized version of GADMM by some rather new and core applications in statistical learning. Code packages in Matlab for these applications are also developed.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 2, June 2015
Solving network design problems via iterative aggregation
Andreas Bärmann, Frauke Liers, Alexander Martin, Maximilian Merkert, Christoph Thurner, Dieter Weninger
In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly finegrained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 2, June 2015
On solving a hard quadratic 3dimensional assignment problem
Hans D. Mittelmann, Domenico Salvagnin
We address the solution of a very challenging (and previously unsolved) instance of the quadratic 3dimensional assignment problem, arising in digitalwireless communications.The paper describes the techniques developed to solve this instance to optimality, from the choice of an appropriate mixedinteger programming formulation, to cutting planes and symmetry handling. Using these techniques we were able to solve the target instance with moderate computational effort (2.5 million nodes and 1 week of computations on a standard PC).
Full Text: PDF
MPC 2015, ISSUE 1
Mathematical Programming Computation, Volume 7, Issue 1, March 2015
Global optimization of nonconvex problems with multilinear intermediates
Xiaowei Bao, Aida Khajavirad, Nikolaos V. Sahinidis, Mohit Tawarmalani
We consider global optimization of nonconvex problems containing mul tilinear functions. It is well known that the convex hull of a multilinear function over a box is polyhedral, and the facets of this polyhedron can be obtained by solving a linear optimization problem (LP). When used as cutting planes, these facets can sig nificantly enhance the quality of conventional relaxations in generalpurpose global solvers. However, in general, the size of this LP grows exponentially with the number of variables in the multilinear function. To cope with this growth, we propose a graph decomposition scheme that exploits the structure of a multilinear function to decom pose it to lowerdimensional components, for which the aforementioned LP can be solved very efficiently by employing a customized simplex algorithm. We embed this cutting plane generation strategy at every node of the branchandreduce global solver BARON, and carry out an extensive computational study on quadratically constrained quadratic problems, multilinear problems, and polynomial optimization problems. Results show that the proposed multilinear cuts enable BARON to solve many more problems to global optimality and lead to an average 60 % CPU time reduction.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 1, March 2015
Alternating proximal gradient method for sparse nonnegative Tucker decomposition
Yangyang Xu
Multiwaydataarisesinmanyapplicationssuchaselectroencephalography classification, face recognition, text mining and hyperspectral data analysis. Tensor decomposition has been commonly used to find the hidden factors and elicit the intrin sic structures of the multiway data. This paper considers sparse nonnegative Tucker decomposition (NTD), which is to decompose a given tensor into the product of a core tensor and several factor matrices with sparsity and nonnegativity constraints. An alternating proximal gradient method is applied to solve the problem. The algorithm is then modified to sparse NTD with missing values. Periteration cost of the algorithm is estimated scalable about the data size, and global convergence is established under fairly loose conditions. Numerical experiments on both synthetic and real world data demonstrate its superiority over a few stateoftheart methods for (sparse) NTD from partial and/or full observations. The MATLAB code along with demos are accessible from the author’s homepage.
Full Text: PDF
Mathematical Programming Computation, Volume 7, Issue 1, March 2015
Methods for convex and general quadratic programming
Philip E. Gill, Elizabeth Wong
Computational methods are considered for finding a point that satisfies the secondorder necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an activeset method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equalityconstrained subproblem involving a “working set” of linearly independent constraints. The method is a reformulation of a method for general QP first proposed by Fletcher, and modified subsequently by Gould. The reformulation facilitates a simpler analysis and has the benefit that the algorithm reduces to a variant of the simplex method when the QP is a linear program. The search direction is computed from a KKT system formed from the QP Hessian and the gradients of the workingset constraints. It is shown that, under certain circumstances, the solution of this KKT system may be updated using a simple recurrence relation, thereby giving a significant reduction in the number of KKT systems that need to be solved. The second part of the paper focuses on the solution of QP problems with constraints in socalled standard form. We describe how the constituent KKT systems are solved, and discuss how an initial basis is defined. Numerical results are presented for all QPs in the CUTEst test collection.
Full Text: PDF
MPC 2014, ISSUE 4
Mathematical Programming Computation, Volume 6, Issue 4, December 2014
qpOASES: a parametric activeset algorithm for quadratic programming
Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, Moritz Diehl
Many practical applications lead to optimization problems that can either be stated as quadratic programming (QP) problems or require the solution ofQP problems on a lower algorithmic level. One relatively recent approach to solve QP problems are parametric activeset methods that are based on tracing the solution along a linear homotopy between a QP problem with known solution and the QP problem to be solved. This approach seems to make them particularly suited for applications where apriori information can be used to speedup the QP solution or where high solution accuracy is required. In this paper we describe the opensource C++ software package qpOASES,which implements a parametric activesetmethod in a reliable and efficient way. Numerical tests show that qpOASES can outperform other popular academic and commercial QP solvers on small to mediumscale convex test examples of theMarosMészáros QP collection. Moreover, various interfaces to thirdparty software packages make it easy to use, even on embedded computer hardware. Finally, we describe how qpOASES can be used to compute critical points of nonconvex QP problems.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 4, December 2014
Branchandcut for complementarityconstrained optimization
Ismael R. de Farias Jr., Ernee Kozyreff, Ming Zhao
We report and analyze the results of our computational testing of branchandcut for the complementarityconstrained optimization problem (CCOP). Besides theMIP cuts commonly present in commercial optimization software,weused inequalities that explore complementarity constraints. To do so,we generalized two families of cuts proposed earlier by de Farias, Johnson, and Nemhauser that had never been tested computationally. Our test problems consisted of linear, binary, and general integer programs with complementarity constraints. Our results on the use of complementarity cuts within a major commercial optimization solver show that they are of critical importance to tackling difficult CCOP instances, typically reducing the computational time required to solve them tremendously.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 4, December 2014
Using symmetry to optimize over the Sherali–Adams relaxation
James Ostrowski
In this paper we examine the impact of using the Sherali–Adams procedure on highly symmetric integer programming problems. Linear relaxations of the extended formulations generated by Sherali–Adams can be very large, containing O ((n,d)) many variables for the leveld closure. When large amounts of symmetry are present in the problem instance however, the symmetry can be used to generate a much smaller linear program that has an identical objective value. We demonstrate this by computing the bound associated with the level 1, 2, and 3 relaxations of several highly symmetric binary integer programming problems. We also present a class of constraints, called counting constraints, that further improves the bound, and in some cases provides a tight formulation. A major advantage of the Sherali–Adams formulation over the traditional formulation is that symmetrybreaking constraints can be more efficiently implemented. We show that using the Sherali–Adams formulation in conjunction with the symmetry breaking tool isomorphism pruning can lead to the pruning of more nodes early on in the branchandbound process.
Full Text: PDF
MPC 2014, ISSUE 3
Mathematical Programming Computation, Volume 6, Issue 3, September 2014
An exact cooperative method for the uncapacitated facility location problem
Marius Posta, Jacques A. Ferland, Philippe Michelon
In this paper, we present a cooperative primaldual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a knownand effective tabu search procedure, and a dual process, which performs a lagrangian branchandbound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branchandbound nodes: decisionvariable bound tightening rules applied at each node, and a subgradient caching strategy to improve the bundle method applied at each node.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 3, September 2014
Optimization of algorithms with OPAL
Charles Audet, KienCong Dang, Dominique Orban
Opal is a generalpurpose system for modeling and solving algorithm optimization problems. Opal takes an algorithm as input, and as output it suggests parameter values that maximize some userdefined performance measure. In order to achieve this, the user provides a Python script describing how to launch the target algorithm, and defining the performance measure. Opal then models this question as a blackbox optimization problem which is then solved by a stateoftheart direct search solver. Opal handles a wide variety of parameter types, it can exploit multiple processors in parallel at different levels, and can take advantage of a surrogate blackbox. Several features of Opal are illustrated on a problem consisting in the design of a hybrid sort strategy.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 3, September 2014
Boosting the feasibility pump
Natashia L. Boland, Andrew C. Eberhard, Faramroze G. Engineer, Matteo Fischetti, Martin W. P. Savelsbergh, Angelos Tsoukalas
The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 3, September 2014
A partial proximal point algorithm for nuclear norm regularized matrix least squares problems
Kaifeng Jiang, Defeng Sun, KimChuan Toh
We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint nondegeneracy condition, together with the strong semismoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from lowrank approximations of transition matrices show that our algorithm is efficient and robust.
Full Text: PDF
MPC 2014, ISSUE 2
Mathematical Programming Computation, Volume 6, Issue 2, June 2014
A firstorder blockdecomposition method for solving twoeasyblock structured semidefinite programs
Renato D. C. Monteiro, Camilo Ortiz, Benar F. Svaiter
In this paper, we consider a firstorder blockdecomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredi ents from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks. We then specialize the method to the context of conic semidefinite programming (SDP) problems consisting of two easy blocks of constraints. Without putting them in standard form, we show that four important classes of graphrelated conic SDP problems auto matically possess the above twoeasyblock structure, namely: SDPs for Ofunctions and O+functions of graph stable set problems, and SDP relaxations of binary inte ger quadratic and frequency assignment problems. Finally, we present computational results on the aforementioned classes of SDPs showing that our method outperforms the three most competitive codes for largescale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a NewtonCG augmented Lagrangian method, called SDPNAL, by Zhao et al., and a variant of the BP method, called the SPDAD method, by Wen et al.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 2, June 2014
A Newton’s method for the continuous quadratic knapsack problem
Roberto Cominetti, Walter F. Mascarenhas, Paulo J. S. Silva
We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in dif ferent contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n2). Numerical experiments show that in practice the method con verges in a small number of iterations with overall linear complexity, and is faster than the stateoftheart algorithms based on median finding, variable fixing, and secant techniques.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 2, June 2014
A branchandprice algorithm for the multidepot heterogeneousfleet pickup and delivery problem with soft time windows
Andrea Bettinelli, Alberto Ceselli, Giovanni Righini
The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongo ing industrial project. First we propose an exact branchandprice algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.
Full Text: PDF
MPC 2014, ISSUE 1
Mathematical Programming Computation, Volume 6, Issue 1, March 2014
Matrixfree interior point method for compressed sensing problems
Kimon Fountoulakis, Jacek Gondzio, Pavel Zhlobich
We consider a class of optimization problems for sparse signal reconstruction which arise in the field of compressed sensing (CS). A plethora of approaches and solvers exist for such problems, for example GPSR, FPC_AS, SPGL1, NestA, 1 L(1)_L(s), PDCO to mention a few. CS applications lead to very well conditioned optimization problems and therefore can be solved easily by simple firstorder methods. Interior point methods (IPMs) rely on the Newton method hence they use the secondorder information. They have numerous advantageous features and one clear drawback: being the secondorder approach they need to solve linear equations and this operation has (in the general dense case) an O(n3) computational complexity. Attempts have been made to specialize IPMs to sparse reconstruction problems and they have led to interesting developments implemented in L(1)_L(s) and PDCO softwares. We go a few steps further. First, we use the matrixfree IPM, an approach which redesigns IPM to avoid the need to explicitly formulate (and store) the Newton equation systems. Secondly, we exploit the special features of the signal processing matrices within the matrixfree IPM. Two such features are of particular interest: an excellent conditioning of these matrices and the ability to perform inexpensive (low complexity) matrix–vector multiplications with them. Computational experience with large scale onedimensional signals confirms that the new approach is efficient and offers an attractive alternative to other stateoftheart solvers.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 1, March 2014
RENS
Timo Berthold
This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a subMINLP to explore the set of feasible roundings of an optimal solution ¯ x of a linear or nonlinear relaxation. The subMINLP is constructed by fixing integer variables x j with ¯ x j ? Z and bounding the remaining integer variables to x j ? {¯x j , ¯x j }. We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the socalled roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branchcutandprice framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLPs, using solely software which is available in source code. It turns out that for these problem classes 60 to 70% of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 1, March 2014
Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem
Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, Serguei Rossomakhine
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order n. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly n snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by kopt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in n3 major iterations.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 1, March 2014
Block splitting for distributed optimization
Neal Parikh, Stephen Boyd
This paper describes a general purposemethod for solving convex optimization problems in a distributed computing environment. In particular, if the problem data includes a large linear operator or matrix A, the method allows for handling eachsubblock of A on a separatemachine. The approach works as follows. First, we define a canonical problem form called graph form, in which we have two sets of variables related by a linear operator A, such that the objective function is separable across these two sets of variables. Many types of problems are easily expressed in graph form, including cone programs and a wide variety of regularized loss minimization problems from statistics, like logistic regression, the support vector machine, and the lasso. Next, we describe graph projection splitting, a form of Douglas–Rachford splitting or the alternating direction method of multipliers, to solve graph form problems serially. Finally, we derive a distributed block splitting algorithm based on graph projection splitting. In a statistical or machine learning context, this allows for training models exactly with a huge number of both training examples and features, such that each processor handles only a subset of both. To the best of our knowledge, this is the only general purpose method with this property. We present several numerical experiments in both the serial and distributed settings.
Full Text: PDF
MPC 2013, ISSUE 4
Mathematical Programming Computation, Volume 5, Issue 4, December 2013
On the safety of Gomory cut generators
Gérard Cornuéjols, François Margot, Giacomo Nannicini
Gomory mixedinteger cuts are one of the key components in BranchandCut solvers for mixedinteger linear programs. The textbook formula for generating these cuts is not used directly in opensource and commercial software that work in finite precision: Additional steps are performed to avoid the generation of invalid cuts due to the limited numerical precision of the computations. This paper studies the impact of some of these steps on the safety of Gomory mixedinteger cut generators. As the generation of invalid cuts is a relatively rare event, the experimental design for this study is particularly important. We propose an experimental setup that allows statistically significant comparisons of generators. We also propose a parameter optimization algorithm and use it to find a Gomory mixedinteger cut generator that is as safe as a benchmark cut generator from a commercial solver even though it generates many more cuts.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 4, December 2013
Branchandcut approaches for chanceconstrained formulations of reliable network design problems
Yongjia Song, James R. Luedtke
We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least 1?, where is a risk tolerance.We consider two types of connectivity requirements. We first study the problem of requiring an st path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability.We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branchandcut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facetinducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branchandcut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.
Full Text: PDF
MPC 2013, ISSUE 3
Mathematical Programming Computation, Volume 5, Issue 3, September 2013
TACO: a toolkit for AMPL control optimization
Christian Kirches, Sven Leyffer
We describe a set of extensions to the AMPL modeling language to conveniently model mixedinteger optimal control problems forODEorDAE dynamic processes. These extensions are realized as AMPL user functions and suffixes and do not require intrusive changes to theAMPL language standard or implementation itself. We describe and provide TACO, a Toolkit for AMPL Control Optimization that reads AMPL stub.nl files and detects the structure of the optimal control problem. This toolkit is designed to facilitate the coupling of existing optimal control software packages to AMPL.We discuss requirements, capabilities, and the current implementation. Using the example of the multiple shooting code for optimal control MUSCODII, a direct and simultaneous method for DAEconstrained optimal control, we demonstrate how the problem information provided by the TACO toolkit is interfaced to the solver. In addition, we show how the MSMINTOC algorithm for mixedinteger optimal control can be used to efficiently solve mixedinteger optimal control problems modeled in AMPL. We use the AMPL extensions to model three control problem examples and we discuss how those extensions affect the representation of optimal control problems. Solutions to these problems are obtained by usingMUSCODII and MSMINTOC inside the AMPL environment. A collection of further AMPL control models is provided on the web site http://mintoc.de. MUSCODII and MSMINTOC have been made available on the NEOS Server for Optimization, using the TACO toolkit to enable input of AMPL models
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 3, September 2013
GPU accelerated greedy algorithms for compressed sensing
Jeffrey D. Blanchard, Jared Tanner
For appropriate matrix ensembles, greedy algorithms have proven to be an efficient means of solving the combinatorial optimization problem associated with compressed sensing. This paper describes an implementation for graphics processing units (GPU) of hard thresholding, iterative hard thresholding, normalized iterative hard thresholding, hard thresholding pursuit, and a twostage thresholding algorithm based on compressive sampling matching pursuit and subspace pursuit. The GPU acceleration of the former bottleneck, namely the matrix–vector multiplications, transfers a significant portion of the computational burden to the identification of the support set. The software solves highdimensional problems in fractions of a second which permits largescale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70× acceleration over standard Matlab central rocessing unit implementations using automatic multithreading.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 3, September 2013
A hybrid branchandbound approach for exact rational mixedinteger programming
William Cook, Thorsten Koch, Daniel E. Steffy, Kati Wolter
We present an exact rational solver for mixedinteger linear programming that avoids the numerical inaccuracies inherent in the floatingpoint computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LPbased branchandbound, using numericallysafe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floatingpoint branchandbound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and theGMParithmetic library. Computational results are presented for a suite of test instances taken from the Miplib and Mittelmann libraries and for a new collection of numerically difficult instances.
Full Text: PDF
MPC 2013, ISSUE 2
Mathematical Programming Computation, Volume 5, Issue 2, June 2013
Trajectoryfollowing methods for largescale degenerate convex quadratic programming
Nicholas I. M. Gould, Dominique Orban, Daniel P. Robinson
We consider a class of infeasible, pathfollowing methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An implementation, CQP, is available as part of GALAHAD. We illustrate the advantages of our approach on the CUTEr and Maros–Meszaros test sets.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 2, June 2013
Efficient blockcoordinate descent algorithms for the Group Lasso
Zhiwei Qin, Katya Scheinberg, Donald Goldfarb
We present two algorithms to solve the Group Lasso problem (Yuan and Lin in, J R Stat Soc Ser B (Stat Methodol) 68(1):49–67, 2006). First, we propose a general version of the Block Coordinate Descent (BCD) algorithm for the Group Lasso that employs an efficient approach for optimizing each subproblem exactly.We show that it exhibits excellent performance when the groups are of moderate size. For groups of large size, we propose an extension of ISTA/FISTA SIAM (Beck and Teboulle in, SIAM J Imag Sci 2(1):183–202, 2009) based on variable steplengths that can be viewed as a simplified version of BCD. By combining the two approaches we obtain an implementation that is very competitive and often outperforms other stateoftheart approaches for this problem. We show how these methods fit into the globally convergent general block coordinate gradient descent framework in Tseng and Yun (Math Program 117(1):387–423, 2009). We also show that the proposed approach is more efficient in practice than the one implemented in Tseng and Yun (Math Program 117(1):387–423, 2009). In addition, we apply our algorithms to the Multiple Measurement Vector (MMV) recovery problem, which can be viewed as a special case of the Group Lasso problem, and compare their performance to other methods in this particular instance.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 2, June 2013
Local cuts for mixedinteger programming
Vašek Chvátal, William Cook, Daniel Espinoza
A general framework for cuttingplane generation was proposed by Applegate et al. in the context of the traveling salesman problem. The process considers the image of a problem space under a linear mapping, chosen so that a relaxation of the mapped problem can be solved efficiently. Optimization in the mapped space can be used to find a separating hyperplane, if one exists, and via substitution this gives a cutting plane in the original space.We extend this procedure to general mixedinteger programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floatingpoint arithmetic and in rational arithmetic.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 2, June 2013
Parallel stochastic gradient algorithms for largescale matrix completion
Benjamin Recht, Christopher Ré
This paper develops Jellyfish, an algorithm for solving dataprocessing problems with matrixvalued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and leastsquares problems regularized by the nuclear norm or ?2norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speedup nearly proportional to the number of processors. On largescale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 h, while Jellyfish solves the same problem in under 3 min on a 12 core workstation.
Full Text: PDF
MPC 2013, ISSUE 1
Mathematical Programming Computation, Volume 5, Issue 1, March 2013
Warmstarting the homogeneous and selfdual interior point method for linear and conic quadratic problems
Anders Skajaa, Erling D. Andersen, Yinyu Ye
We present two strategies for warmstarting primaldual interior point methods for the homogeneous selfdual 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 blackbox 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 worstcase 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 facetdefining cuts.We obtain good computational results with a branchcutandprice 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
Branchandcut for separable piecewise linear optimization and intersection with semicontinuous constraints
I. R. de Farias Jr, E. Kozyreff, R. Gupta, M. Zhao
We report and analyze the results of our computational testing of branchandcut 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 branchandcut. Finally, we report and analyze results on piecewise linear optimization problems with semicontinuous constraints.
Full Text: PDF
MPC 2012, ISSUE 4
Mathematical Programming Computation, Volume 4, Issue 4, December 2012
Optimal sensitivity based on IPOPT
Hans Pirnay, Rodrigo LópezNegrete, L. T. Biegler
We introduce a flexible, open source implementation that provides the optimal sensitivity of solutions of nonlinear programming (NLP) problems, and is adapted to a fast solver based on a barrier NLP method. The program, called sIPOPT evaluates the sensitivity of the Karush–Kuhn–Tucker (KKT) system with respect to perturbation parameters. It is paired with the opensource IPOPT NLP solver and reuses matrix factorizations from the solver, so that sensitivities to parameters are determined with minimal computational cost. Aside from estimating sensitivities for parametric NLPs, the program provides approximate NLP solutions for nonlinear model predictive control and state estimation. These are enabled by prefactored KKT matrices and a fixrelax strategy based on Schur complements. In addition, reduced Hessians are obtained at minimal cost and these are particularly effective to approximate covariance matrices in parameter and state estimation problems. The sIPOPT program is demonstrated on four case studies to illustrate all of these features.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 4, December 2012
Solving a lowrank factorization model for matrix completion by a nonlinear successive overrelaxation algorithm
Zaiwen Wen, W. Yin, Y. Zhang
Thematrix completion problem is to recover a lowrank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclearnorm minimization which requires computing singular value decompositions—a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving largescale problems, we propose a lowrank factorization model and construct a nonlinear successive overrelaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclearnorm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 4, December 2012
Maximumweight stable sets and safe lower bounds for graph coloring
Stephan Held, William Cook, Edward C. Sewell
The best method known for determining lower bounds on the vertex coloring number of a graph is the linearprogramming columngeneration technique, where variables correspond to stable sets, first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numericallysafe results, independent of the floatingpoint accuracy of linearprogramming software. Our work includes an improved branchandbound algorithm for maximumweight stable sets and a parallel branchandprice framework for graph coloring. Computational results are presented on a collection of standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 4, December 2012
A comparative study of SQPtype algorithms for nonlinear and nonconvex mixedinteger optimization
Oliver Exler, Thomas Lehmann, Klaus Schittkowski
We present numerical results of a comparative study of codes for nonlinear and nonconvex mixedinteger optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by trustregions, linear outer approximations, and branchandbound techniques. The mixedinteger quadratic programming subproblems are solved by a branchandcut algorithm. Second order information is updated by a quasiNewton update formula (BFGS) applied to the Lagrange function for continuous, but also for integer variables. We do not require that the model functions can be evaluated at fractional values of the integer variables. Thus, partial derivatives with respect to integer variables are replaced by descent directions obtained from function values at neighboring grid points, and the number of simulations or function evaluations, respectively, is our main performance criterion to measure the efficiency of a code. Numerical results are presented for a set of 100 academic mixedinteger test problems. Since not all of our test examples are convex, we reach the bestknown solutions in about 90 % of the test runs, but at least feasible solutions in the other cases. The average number of function evaluations of the new mixedinteger SQP code is between 240 and 500 including those needed for one or twosided approximations of partial derivatives or descent directions, respectively. In addition, we present numerical results for a set of 55 test problems with some practical
Full Text: PDF
MPC 2012, ISSUE 3
Mathematical Programming Computation, Volume 4, Issue 3, September 2012
A computational study of a solver system for processing twostage stochastic LPs with enhanced Benders decomposition
Victor Zverovich, Csaba I. Fabian, Eldon F. D. Ellison, Gautam Mitra
We report a computational study of twostage SP models on a large set of benchmark problems and consider the following methods: (i) Solution of the deter ministic equivalent problem by the simplex method and an interior point method, (ii) Benders decomposition (Lshaped method with aggregated cuts), (iii) Regular ised decomposition of Ruszczyn ?ski (Math Program 35:309–333, 1986), (iv) Bend ers decomposition with regularization of the expected recourse by the level method (Lemare?chal et al. in Math Program 69:111–147, 1995), (v) Trust region (regularisa tion) method of Linderoth and Wright (Comput Optim Appl 24:207–250, 2003). In this study the three regularisation methods have been introduced within the computational structure of Benders decomposition. Thus secondstage infeasibility is controlled in the traditional manner, by imposing feasibility cuts. This approach allows extensions of the regularisation to feasibility issues, as in Fa?bia?n and Szo ?ke (Comput Manag Sci 4:313–353, 2007). We report computational results for a wide range of benchmark problems from the POSTS and SLPTESTSET collections and a collection of difficult test problems compiled by us. Finally the scaleup properties and the performance profiles of the methods are presented.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 3, September 2012
Cutting plane versus compact formulations for uncertain (integer) linear programs
Matteo Fischetti, Michele Monaci
Robustness is about reducing the feasible set of a given nominal opti mization problem by cutting “risky” solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization a? la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magni tude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better perfor mance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 3, September 2012
LP and SDP branchandcut algorithms for the minimum graph bisection problem: a computational comparison
Michael Armbruster, Marzena Fügenschuh, Christoph Helmberg, Alexander Martin
While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semi definite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semi definite approaches for large sparse instances, we set up a common branchandcut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound prof its much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch andcut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.
Full Text: PDF
MPC 2012, ISSUE 2
Mathematical Programming Computation, Volume 4, Issue 2, June 2012
PySP: modeling and solving stochastic programs in Python
JeanPaul Watson, David L. Woodruff, William E. Hart
Although stochastic programming is a powerful tool for modeling deci sionmaking under uncertainty, various impediments have historically prevented its widespread use. One factor involves the ability of nonspecialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixedinteger, nonlinear, and/or multistage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable runtimes on largescale problems. We simul taneously address both of these factors in our PySP software package, which is part of the Coopr opensource Python repository for optimization; the latter is distributed as part of IBM’s COINOR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, nonlinear, and mixedinteger components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo opensource algebraic model ing language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multistage stochastic programs. By leveraging the combination of a highlevel programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide com pletely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 2, June 2012
On optimizing over liftandproject closures
Pierre Bonami
The strengthened liftandproject closure of a mixed integer linear pro gram is the polyhedron obtained by intersecting all strengthened liftandproject cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relax ation. In this paper, we present an algorithm for approximately optimizing over the strengthened liftandproject closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunc tive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened liftandproject closure. Finally, we present computational experiments and comparisons with recent related works.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 2, June 2012
A penaltyinteriorpoint algorithm for nonlinear constrained optimization
Frank E. Curtis
Penalty and interiorpoint methods for nonlinear optimization problems have enjoyed great successes for decades. Penalty methods have proved to be effective for a variety of problem classes due to their regularization effects on the constraints. They have also been shown to allow for rapid infeasibility detection. Interiorpoint methods have become the workhorse in largescale optimization due to their New tonlike qualities, both in terms of their scalability and convergence behavior. Each of these two strategies, however, have certain disadvantages that make their use either impractical or inefficient for certain classes of problems. The goal of this paper is to present a penaltyinteriorpoint method that possesses the advantages of penalty and interiorpoint techniques, but does not suffer from their disadvantages. Numerous attempts have been made along these lines in recent years, each with varying degrees of success. The novel feature of the algorithm in this paper is that our focus is not only on the formulation of the penaltyinteriorpoint subproblem itself, but on the design of updates for the penalty and interiorpoint parameters. The updates we propose are designed so that rapid convergence to a solution of the nonlinear optimization problem or an infeasible stationary point is attained. We motivate the convergence properties of our algorithm and illustrate its practical performance on large sets of problems, including sets of problems that exhibit degeneracy or are infeasible.
Full Text: PDF
MPC 2012, ISSUE 1
Mathematical Programming Computation, Volume 4, Issue 1, March 2012
Roundingbased heuristics for nonconvex MINLPs
Giacomo Nannicini, Pietro Belotti
We propose two primal heuristics for nonconvex mixedinteger nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixedinteger linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within an opensource solver for nonconvex mixedinteger nonlinear programs.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 1, March 2012
Globally solving nonconvex quadratic programming problems via completely positive programming
Jieqiu Chen, Samuel Burer
Nonconvex quadratic programming (QP) is an NPhard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the firstorder KKT conditions and polyhedralsemidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 1, March 2012
Fast Fourier optimization
Robert J. Vanderbei
Many interesting and fundamentally practical optimization problems, ranging from optics, to signal processing, to radar and acoustics, involve constraints on the Fourier transform of a function. It is wellknown that the fast Fourier transform (fft) is a recursive algorithm that can dramatically improve the efficiency for computing the discrete Fourier transform. However, because it is recursive, it is difficult to embed into a linear optimization problem. In this paper, we explain the main idea behind the fast Fourier transform and show how to adapt it in such a manner as to make it encodable as constraints in an optimization problem. We demonstrate a realworld problem from the field of highcontrast imaging. On this problem, dramatic improvements are translated to an ability to solve problems with a much finer grid of discretized points. As we shall show, in general, the “fast Fourier” version of the optimization constraints produces a larger but sparser constraint matrix and therefore one can think of the fast Fourier transform as a method of sparsifying the constraints in an optimization problem, which is usually a good thing.
Full Text: PDF
Mathematical Programming Computation, Volume 4, Issue 1, March 2012
A primal–dual regularized interiorpoint method for convex quadratic programs
M. P. Friedlander, D. Orban
Interiorpoint methods in augmented form for linear and convex quadratic programming require the solution of a sequence of symmetric indefinite linear systems which are used to derive search directions. Safeguards are typically required in order to handle free variables or rankdeficient Jacobians. We propose a consistent framework and accompanying theoretical justification for regularizing these linear systems. Our approach can be interpreted as a simultaneous proximalpoint regularization of the primal and dual problems. The regularization is termed exact to emphasize that, although the problems are regularized, the algorithm recovers a solution of the original problem, for appropriate values of the regularization parameters.
Full Text: PDF
MPC 2011, ISSUE 4
Mathematical Programming Computation, Volume 3, Issue 4, December 2011
Practical strategies for generating rank1 split cuts in mixedinteger linear programming
Gerard Cornuéjols, Giacomo Nannicini
In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixedinteger cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, ReduceandSplit, LiftandProject, Flow and Knapsack cover): onMIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a BranchandCut framework, these new cuts can improve computing time on difficult instances.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 4, December 2011
A factorization with update procedures for a KKT matrix arising in direct optimal control
Christian Kirches, Hans Georg Bock, Johannes P. Schlöder, Sebastian Sager
Quadratic programs obtained for optimal control problems of dynamic or discretetime processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fillin. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 4, December 2011
A recipe for finding good solutions to MINLPs
Leo Liberti, Nenad Mladenovic, Giacomo Nannicini
Finding good (or even just feasible) solutions forMixedInteger Nonlinear Programming problems independently of the specific problem structure is a very hard but practically important task, especially when the objective and/or the constraints are nonconvex. With this goal in mind, we present a generalpurpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and BranchandBound.We test the proposed approach on MINLPLib, comparing with several existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP solvers with an AMPL interface as the main search tools.
Full Text: PDF
MPC 2011, ISSUE 3
Mathematical Programming Computation, Volume 3, Issue 3, August 2011
Templates for convex cone problems with applications to sparse signal recovery
Stephen R. Becker, Emmanuel J. Candès, Michael C. Grant
This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal firstorder method. A merit of this approach is its flexibility: for example, all compressed sensing problems can be solved via this approach. These include models with objective functionals such as the totalvariation norm, Wx1 where W is arbitrary, or a combination thereof. In addition, the paper introduces a number of technical contributions such as a novel continuation scheme and a novel approach for controlling the step size, and applies results showing that the smooth and unsmoothed problems are sometimes formally equivalent. Combined with our framework, these lead to novel, stable and computationally efficient algorithms. For instance, our general implementation is competitive with stateoftheart methods for solving intensively studied problems such as the LASSO. Further, numerical experiments show that one can solve the Dantzig selector problem, for which no efficient largescale solvers exist, in a few hundred iterations. Finally, the paper is accompanied with a software release. This software is not a single, monolithic solver; rather, it is a suite of programs and routines designed to serve as building blocks for constructing complete algorithms.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 3, August 2011
Pyomo: modeling and solving mathematical programs in Python
Hart E. Hart, JeanPaul Watson, David L. Woodruff
We describe Pyomo, an open source software package for modeling and solving mathematical programs in Python. Pyomo can be used to define abstract and concrete problems, create problem instances, and solve these instances with standard opensource and commercial solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages such as AMPL, AIMMS, and GAMS. In contrast, Pyomo’s modeling objects are embedded within a fullfeatured highlevel programming language with a rich set of supporting libraries. Pyomo leverages the capabilities of the Coopr software library, which together with Pyomo is part of IBM’s COINOR opensource initiative for operations research software. Coopr integrates Python packages for defining optimizers, modeling optimization applications, and managing computational experiments. Numerous examples illustrating advanced scripting applications are provided.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 3, August 2011
Optimal linear arrangements using betweenness variables
Alberto Caprara, Marcus Oswald, Gerhard Reinelt, Robert Schwarz, Emiliano Traversi
We solve for the first time to proven optimality the small instances in the classical literature benchmark of Minimum Linear Arrangement. This is achieved by formulating the problem as an ILP in a somehow unintuitive way, using variables expressing the fact that a vertex is between two other adjacent vertices in the arrangement. Using (only) these variables appears to be the key idea of the approach. Indeed, with these variables already the use of very simple constraints leads to good results, which can however be improvedwith amore detailed study of the underlying polytope.
Full Text: PDF
MPC 2011, ISSUE 2
Mathematical Programming Computation, Volume 3, Issue 2, June 2011
A relaxandcut framework for Gomory mixedinteger cuts
Matteo Fischetti, Domenico Salvagnin
Gomory mixedinteger cuts (GMICs) are widely used in modern branchandcut codes for the solution of mixedinteger programs. Typically, GMICs are iteratively generated from the optimal basis of the current linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank1 GMICs read from a basis of the original LP—the one before the addition of any cut.We adopt a relaxandcut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast—yet accurate—variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cutandbranch enumerative framework.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 2, June 2011
MIPLIB 2010  Mixed Integer Programming Library version 5
Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E. Bixby, Emilie Danna, Gerald Gamrath, Ambros M. Gleixner, Stefan Heinz, Andrea Lodi, Hans Mittelmann, Ted Ralphs, Domenico Salvagnin, Daniel E. Steffy, Kati Wolter
This paper reports on the fifth version of theMixed Integer Programming Library. The miplib 2010 is the first miplib release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today’s codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
Full Text: PDF
MPC 2011, ISSUE 1
Mathematical Programming Computation, Volume 3, Issue 1, March 2011
Faster min–max resource sharing in theory and practice
Dirk Müller, Klaus Radke, Jens Vygen
We consider the (blockangular) min–max resource sharing problem, which is defined as follows. Given finite sets of resources and of customers, a convex set c, called block, and a convex function gc:cR+ for every c, the task is to find bcc (c) approximately attaining :=infmaxrc(gc(bc))rbcc (c) . As usual we assume that g c can be computed efficiently and we have a constant ? ? 1 and oracle functions fc:R+c, called block solvers, which for c and yR+ return an element bcc with ygc(bc)infbcygc(b). We describe a simple algorithm which solves this problem with an approximation guarantee ?(1 + ?) for any ? > 0, and whose running time is O((+)log(loglog+?2)) for any fixed ? ? 1, where ? is the time for an oracle call. This generalizes and improves various previous results. We also prove other bounds and describe several speedup techniques. In particular, we show how to parallelize the algorithm efficiently. In addition we review another algorithm, variants of which were studied before. We show that this algorithm is almost as fast in theory, but it was not competitive in our experiments. Our work was motivated mainly by global routing in chip design. Here the blocks are mixedinteger sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. Our algorithm solves these instances nearly optimally in less than two hours.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 1, March 2011
Quadratic factorization heuristics for copositive programming
Immanuel M. Bomze, Florian Jarre, Franz Rendl
Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NPhard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.
Full Text: PDF
Mathematical Programming Computation, Volume 3, Issue 1, March 2011
Computing compatible tours for the symmetric traveling salesman problem
Matteo Fortini, Adam N. Letchford, Andrea Lodi, Klaus M. Wenger
We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x?, and then find the best tour ¯ x that is compatible with x?, where compatible means that every subtour elimination constraint that is satisfied at equality at x? is also satisfied at equality at ¯ x. We prove that finding the best compatible tour is NPhard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branchandcut algorithm for computing the best compatible tour, and present extensive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.
Full Text: PDF
MPC 2010, ISSUE 34
Mathematical Programming Computation, Volume 2, Issue 34, December 2010
Implementation of nonsymmetric interiorpoint methods for linear optimization over sparse matrix cones
Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe
We describe an implementation of nonsymmetric interiorpoint methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones.We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interiorpoint solvers for semidefinite programming.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 34, December 2010
Alternating direction augmented Lagrangian methods for semidefinite programming
Zaiwen Wen, Donald Goldfarb, Wotao Yin
We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixedpoint argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 34, December 2010
A heuristic to generate rank1 GMI cuts
Sanjeeb Dash, Marcos Goycoolea
Gomory mixedinteger (GMI) cuts are among the most effective cutting planes for general mixedinteger programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of a MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank1 mixedinteger rounding cuts. Further, we use our heuristic to generate globally valid rank1 GMI cuts at nodes of a branchandcut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problemspecific cuts.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 34, December 2010
Exact algorithm over an arctimeindexed formulation for parallel machine scheduling problems
Artur Pessoa, Eduardo Uchoa, Marcus Poggi de Aragão, Rosiane Rodrigues
This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time.We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P\sum{wj Tj} problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that mediumsized instances of the P\sum{wj Tj} have been solved to optimality.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 34, December 2010
An inexact interior point method for L1regularized sparse covariance selection
Lu Li, KimChuan Toh
Sparse covariance selection problems can be formulated as logdeterminant (logdet) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interiorpoint methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual pathfollowing interiorpoint algorithm for solving large scale logdet SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and illconditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and illconditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.
Full Text: PDF
MPC 2010, ISSUE 2
Mathematical Programming Computation, Volume 2, Issue 2, June 2010
A library of local search heuristics for the vehicle routing problem
Chris Groër, Bruce Golden, Edward Wasil
The vehicle routing problem (VRP) is a difficult and wellstudied combinatorial optimization problem. Realworld instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, objectoriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is welldocumented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the bestknown solution on benchmark problems.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 2, June 2010
Efficient highprecision matrix algebra on parallel architectures for nonlinear combinatorial optimization
John Gunnels, Jon Lee, Susan Margulies
We provide a first demonstration of the idea that matrixbased algorithms for nonlinear combinatorial optimization problems can be efficiently implemented. Such algorithms were mainly conceived by theoretical computer scientists for proving efficiency. We are able to demonstrate the practicality of our approach by developing an implementation on a massively parallel architecture, and exploiting scalable and efficient parallel implementations of algorithms for ultra highprecision linear algebra. Additionally, we have delineated and implemented the necessary algorithmic and coding changes required in order to address problems several orders of magnitude larger, dealing with the limits of scalability from memory footprint, computational efficiency, reliability, and interconnect perspectives.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 2, June 2010
The MCFseparator: detecting and exploiting multicommodity flow structures in MIPs
Tobias Achterberg, Christian Raack
Given a general mixed integer program, we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multicommodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branchandcut libraries of Scip and Cplex. We make use of the complemented mixed integer rounding framework but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speedsup the computation for a large set of mixed integer programs coming from network design problems by a factor two on average.We show that almost 10% of the instances in general testsets contain consistent embedded networks. For these instances the computation time is decreased by 18% on average.
Full Text: PDF
MPC 2010, ISSUE 1
Mathematical Programming Computation, Volume 2, Issue 1, March 2010
Optimizing a polyhedralsemidefinite relaxation of completely positive programs
Samuel Burer
It has recently been shown (Burer, Math Program 120:479–495, 2009) that a large class of NPhard nonconvex quadratic programs (NQPs) can be modeled as socalled completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NPhard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interiorpoint methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPswhile simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of boxconstrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a bestknown lower bound is obtained. We also incorporate the lower bounds within a branchandbound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 1, March 2010
On solving trustregion and other regularised subproblems in optimization
Nicholas I. M. Gould, Daniel P. Robinson, H. Sue Thorne
The solution of trustregion and regularisation subproblems that arise in unconstrained optimization is considered. Building on the pioneering work of Gay, Moré and Sorensen, methods that obtain the solution of a sequence of parametrized linear systems by factorization are used. Enhancements using highorder polynomial approximation and inverse iteration ensure that the resulting method is both globally and asymptotically at least superlinearly convergent in all cases, including the notorious hard case. Numerical experiments validate the effectiveness of our approach. The resulting software is available as packages TRS and RQS as part of the GALAHAD optimization library, and is especially designed for largescale problems.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 1, March 2010
A new relaxation framework for quadratic assignment problems based on matrix splitting
Jiming Peng, Hans Mittelmann, Xiaoxue Li
Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the socalled symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.
Full Text: PDF
MPC 2009, ISSUE 4
Mathematical Programming Computation, Volume 1, Issue 4, December 2009
A structureconveying modelling language for mathematical and stochastic programming
Marco Colombo, Andreas Grothey, Jonathan Hogg, Kristian Woodsend, Jacek Gondzio
We present a structureconveying algebraicmodelling language formathematical programming. The proposed language extends AMPL with objectoriented features that allows the user to construct models from submodels, and is implemented as a combination of pre and postprocessing phases for AMPL. Unlike traditional modelling languages, the new approach does not scramble the block structure of the problem, and thus it enables the passing of this structure on to the solver. Interior point solvers that exploit block linear algebra and decompositionbased solvers can therefore directly take advantage of the problem’s structure. The language contains features to conveniently model stochastic programming problems, although it is designed with a much broader application spectrum.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 4, December 2009
Informationbased branching schemes for binary linear mixed integer problems
Fatma Kilinc Karzan, George L. Nemhauser, Martin W.P. Savelsbergh
Branching variable selection can greatly affect the effectiveness and efficiency of a branchandbound algorithm. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We propose an approach which is empowered by exploiting the information contained in a family of fathomed subproblems, collected beforehand from an incomplete branchandbound tree. In particular, we use this information to define new branching rules that reduce the risk of incurring inappropriate branchings. We provide computational results that demonstrate the effectiveness of the new branching rules on various benchmark instances.
Full Text: PDF
MPC 2009, ISSUE 23
Mathematical Programming Computation, Volume 1, Issue 23, October 2009
Support vector machine classification with indefinite kernels
Ronny Luss, Alexandre d’Aspremont
We propose a method for support vector machine classification using indefinite kernels. Instead of directly minimizing or stabilizing a nonconvex loss function, our algorithm simultaneously computes support vectors and a proxy kernel matrix used in forming the loss. This can be interpreted as a penalized kernel learning problem where indefinite kernel matrices are treated as noisy observations of a true Mercer kernel. Our formulation keeps the problem convex and relatively large problems can be solved efficiently using the projected gradient or analytic center cutting plane methods. We compare the performance of our technique with other methods on several standard data sets.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 23, October 2009
General kopt submoves for the Lin–Kernighan TSP heuristic
Keld Helsgaun
Local search with kexchange neighborhoods, kopt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of kopt in LKH2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH2 is free of charge for academic and noncommercial use and can be downloaded in source code.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 23, October 2009
Generating liftandproject cuts from the LP simplex tableau: open source implementation and testing of new variants
Egon Balas, Pierre Bonami
Liftandproject cuts for mixed integer programs (MIP), derived from a disjunction on an integerconstrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higherdimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of liftandproject (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called
iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 23, October 2009
Feasibility pump 2.0
Matteo Fischetti, Domenico Salvagnin
Finding a feasible solution of a given mixedinteger programming (MIP) model is a very important NPcomplete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a divinglike procedure based on rounding and constraint propagation—a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowingdown the method and with a significantly better quality of the feasible solutions found.
Full Text: PDF
MPC 2009, ISSUE 1
Mathematical Programming Computation, Volume 1, Issue 1, July 2009
SCIP: Solving constraint integer programs
Tobias Achterberg
Constraint integer programming (CIP) is a novel paradigm which integrates constraint programming (CP), mixed integer programming (MIP), and satisfiability (SAT) modeling and solving techniques. In this paper we discuss the software framework and solver SCIP (Solving Constraint Integer Programs), which is free for academic and noncommercial use and can be downloaded in source code.
This paper gives an overview of the main design concepts of SCIP and how it can be used to solve constraint integer programs. To illustrate the performance and flexibility of SCIP, we apply it to two different problem classes. First, we consider mixed integer programming and show by computational experiments that SCIP is almost competitive to specialized commercial MIP solvers, even though SCIP supports the more general constraint integer programming paradigm. We develop new ingredients that improve current MIP solving technology.
As a second application, we employ SCIP to solve chip design verification problems as they arise in the logic design of integrated circuits. This application goes far beyond traditional MIP solving, as it includes several highly nonlinear constraints, which can be handled nicely within the constraint integer programming framework. We show anecdotally how the different solving techniques from MIP, CP, and SAT work together inside SCIP to deal with such constraint classes. Finally, experimental results show that our approach outperforms current stateoftheart techniques for proving the validity of properties on circuits containing arithmetic.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 1, July 2009
Blossom V: a new implementation of a minimum cost perfect matching algorithm
Vladimir Kolmogorov
We describe a new implementation of the Edmonds’s algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the “variable dual updates” approach of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s algorithm. While our use of priority queues does not improve the worstcase complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 1, July 2009
Testing cut generators for mixedinteger linear programming
François Margot
In this paper, a methodology for testing the accuracy and strength of cut generators for mixedinteger linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six ReduceandSplit cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed.
Full Text: PDF
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 20082020 by Zuse Institute Berlin (ZIB).