MPC 2019, ISSUE 4
Mathematical Programming Computation, Volume 11, Issue 4, December 2019
A derivative-free Gauss–Newton method
Coralia Cartis, Lindon Roberts
We present DFO-GN, a derivative-free version of the Gauss–Newton method for solving nonlinear least-squares problems.
DFO-GN uses linear interpolation of residual values to build a quadratic model of the
objective, which is then used within a typical derivative-free trust-region framework. We show that DFO-GN is globally
convergent and requires at most O(??2) iterations to reach approximate first-order criticality within tolerance ?.
We provide an implementation of DFO-GN and compare it to other state-of-the-art derivative-free solvers that use quadratic
interpolation models. We demonstrate numerically that despite using only linear residual models, DFO-GN performs
comparably to these methods in terms of objective evaluations. Furthermore, as a result of the simplified interpolation
procedure, DFO-GN has superior runtime and scalability. Our implementation of DFO-GN 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
Structure-driven fix-and-propagate 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 multi-row facility layout problem (MRFLP) looks for a non-overlapping arrangement of these departments in the rows such that the weighted sum of the center-to-center 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 mixed-integer linear programming formulations for the (space-free) multi-row 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 (space-free) multi-row 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 second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound 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 pseudo-inverse 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 state-of-the art mixed-integer 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 branch-and-bound algorithm, Optimal-SPCA, 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 high-quality 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 floating-point 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 floating-point 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
Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
Yuzixuan Zhu, Gábor Pataki, Quoc Tran-Dinh
We introduce Sieve-SDP, a simple facial reduction algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP 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 real-world 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 cutting-planes for mixed-integer programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure can be computationally costly in practice. For the case of two-row relaxations, we present a practical algorithm that computes trivial lifting coefficients in constant time, for arbitrary maximal lattice-free 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 sub-classes 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 branch-and-cut
Bin Yu, John E. Mitchel, Jong-Shi 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 branch-and-cut 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 big-M 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 QP-based 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 value-at-risk 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 well-suited for branch-and-bound 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 branch-and-bound algorithms. We test the simplex-based quadratic programming algorithms to solve convex as well as discrete instances and compare them with the state-of-the-art 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 speed-up. For smaller discrete instances, the speed-up is about 13x over a barrier-based branch-and-bound algorithm and 6x over the LP-based branch-and-bound 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 decision-making, a widely utilized group decision-making process, requires the consent of all participants. We consider consensus stopping games, a class of stochastic games arising in the context of consensus decision-making 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 NP-hard 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 mixed-integer linear program by a branch-and-cut 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 open-source software framework for numerical optimization. CasADi is a general-purpose 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 self-contained C++, but is most conveniently used via full-featured 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 up-to-date 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 branch-and-cut 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 speed-up 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 mixed-binary 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 mixed-binary 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 (QP-r-NE) subject to linear and convex quadratic constraints that covers many applications and is known to be NP-hard 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 branch-and-bound, to find a globally optimal solution to the underlying QP within a pre-specified ϵ-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 worst-case complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-r-NE 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 2-level polytopes
Adam Bohn, Yuri Faenza, Samuel Fiorini, Vissarion Fisikopoulos, Marco Macchia, Kanstantsin Pashkovich
A (convex) polytope P is said to be 2-level 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 2-level polytopes of a given dimension d, and provide complete experimental results for d⩽7. Our approach is inductive: for each fixed (d−1)-dimensional 2-level polytope P0, we enumerate all d-dimensional 2-level polytopes P that have P0 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 P0, we obtain all 2-level polytopes in dimension d.
Full Text: PDF
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2024 by Zuse Institute Berlin (ZIB).