MPC 2021, ISSUE 4
Mathematical Programming Computation, Volume 12, Issue 4, December 2021
A Benders squared (B^2) framework for infinite-horizon stochastic linear programs
Giacomo Nannicini, Emiliano Traversi, Roberto Wolfler Calvo
We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can guarantee convergence with a given confidence level. The methodology alternates between a forward pass to explore sample paths and determine trial solutions, and a backward pass to generate a polyhedral approximation of the optimal value function by computing subgradients from the dual of the scenario subproblems. A computational study on a large set of randomly generated instances for two classes of problems shows that the proposed algorithm is able to effectively solve instances of moderate size to high precision, provided that the instance structure allows the construction of what we call constant-statepolicies with satisfactory objective function value.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2021
Benders decomposition with adaptive oracles for large scale optimization
Nicolò Mazzi, Andreas Grothey, Ken McKinnon, Nagisa Sugishita
This paper proposes an algorithm to efficiently solve large optimization problems which exhibit a column bounded block-diagonal structure, where subproblems differ in right-hand side and cost coefficients. Similar problems are often tackled using cutting-plane algorithms, which allow for an iterative and decomposed solution of the problem. When solving subproblems is computationally expensive and the set of subproblems is large, cutting-plane algorithms may slow down severely. In this context we propose two novel adaptive oracles that yield inexact information, potentially much faster than solving the subproblem. The first adaptive oracle is used to generate inexact but valid cutting planes, and the second adaptive oracle gives a valid upper bound of the true optimal objective. These two oracles progressively “adapt” towards the true exact oracle if provided with an increasing number of exact solutions, stored throughout the iterations. These adaptive oracles are embedded within a Benders-type algorithm able to handle inexact information. We compare the Benders with adaptive oracles against a standard Benders algorithm on a stochastic investment planning problem. The proposed algorithm shows the capability to substantially reduce the computational effort to obtain an ϵ-optimal solution: an illustrative case is 31.9 times faster for a 1.00% convergence tolerance and 15.4 times faster for a 0.01% tolerance.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2021
A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs
Rohit Kannan, James R. Luedtke
We propose a stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Our approach is based on a bi-objective viewpoint of chance-constrained programs that seeks solutions on the efficient frontier of optimal objective value versus risk of constraints violation. To this end, we construct a reformulated problem whose objective is to minimize the probability of constraints violation subject to deterministic convex constraints (which includes a bound on the objective function value). We adapt existing smoothing-based approaches for chance-constrained problems to derive a convergent sequence of smooth approximations of our reformulated problem, and apply a projected stochastic subgradient algorithm to solve it. In contrast with exterior sampling-based approaches (such as sample average approximation) that approximate the original chance-constrained program with one having finite support, our proposal converges to stationary solutions of a smooth approximation of the original problem, thereby avoiding poor local solutions that may be an artefact of a fixed sample. Our proposal also includes a tailored implementation of the smoothing-based approach that chooses key algorithmic parameters based on problem data. Computational results on four test problems from the literature indicate that our proposed approach can efficiently determine good approximations of the efficient frontier.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2021
Computational aspects of infeasibility analysis in mixed integer programming
Jakob Witzig, Timo Berthold, Stefan Heinz
The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems: conflict graph analysis and dual proof analysis. While conflict graph analysis detects sets of contradicting variable bounds in an implication graph, dual proof analysis derives valid linear constraints from the proof of the dual LP’s unboundedness. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide a comprehensive computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first combined approach that uses both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set Miplib 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.
Full Text: PDF
MPC 2021, ISSUE 3
Mathematical Programming Computation, Volume 13, Issue 3, September 2021
MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, Yuji Shinano
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 3, September 2021
A triangulation and fill-reducing initialization procedure for the simplex algorithm
Nikolaos Ploskas, Nikolaos V. Sahinidis, Nikolaos Samaras
The computation of an initial basis is of great importance for simplex algorithms since it determines to a large extent the number of iterations and the computational effort needed to solve linear programs. We propose three algorithms that aim to construct an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates that are utilized in modern simplex implementations. The algorithms rely on triangulation and fill-reducing ordering techniques that are invoked prior to LU factorization. We compare the performance of the CPLEX 12.6.1 primal and dual simplex algorithms using the proposed starting bases against CPLEX using its default crash procedure over a set of 95 large benchmarks (NETLIB, Kennington, Mészáros, Mittelmann). The best proposed algorithm utilizes METIS (Karypis and Kumar in SIAM J Sci Comput 20:359–392, 1998), produces remarkably sparse starting bases, and results in 5% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. Although the proposed algorithm improves CPLEX’s primal simplex algorithm across all problem types studied in this paper, it performs better on hard problems, i.e., the instances for which the CPLEX default requires over 1000 s. For these problems, the proposed algorithm results in 37% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. The proposed algorithm also reduces the execution time of CPLEX’s dual simplex on hard instances by 10%. For the instances that are most difficult for CPLEX, and for which CPLEX experiences numerical difficulties as it approaches the optimal solution, the best proposed algorithm speeds up CPLEX by more than 10 times. Finally, the proposed algorithms lead to a natural way to parallelize CPLEX with speedups over CPLEX’s dual simplex of 1.2 and 1.3 on two and four cores, respectively.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 3, September 2021
Design and implementation of a modular interior-point solver for linear optimization
Mathieu Tanneau, Miguel F. Anjos, Andrea Lodi
This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements a regularized homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. The solver is written in Julia, thus allowing for a flexible and efficient implementation: Tulip’s algorithmic framework is fully disentangled from linear algebra implementations and from a model’s arithmetic. In particular, this allows to seamlessly integrate specialized routines for structured problems. Extensive computational results are reported. We find that Tulip is competitive with open-source interior-point solvers on the H. Mittelmann’s benchmark of barrier linear programming solvers. Furthermore, we design specialized linear algebra routines for structured master problems in the context of Dantzig–Wolfe decomposition. These routines yield a tenfold speedup on large and dense instances that arise in power systems operation and two-stage stochastic programming, thereby outperforming state-of-the-art commercial interior point method solvers. Finally, we illustrate Tulip’s ability to use different levels of arithmetic precision by solving problems in extended precision.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 3, September 2021
Deterministic global optimization with Gaussian processes embedded
Artur M. Schweidtmann, Dominik Bongartz, Daniel Grothe, Tim Kerkenhoff, Xiaopeng Lin, Jaromił Najman, Alexander Mitsos
Gaussian processes (Kriging) are interpolating data-driven models that are frequently applied in various disciplines. Often, Gaussian processes are trained on datasets and are subsequently embedded as surrogate models in optimization problems. These optimization problems are nonconvex and global optimization is desired. However, previous literature observed computational burdens limiting deterministic global optimization to Gaussian processes trained on few data points. We propose a reduced-space formulation for deterministic global optimization with trained Gaussian processes embedded. For optimization, the branch-and-bound solver branches only on the free variables and McCormick relaxations are propagated through explicit Gaussian process models. The approach also leads to significantly smaller and computationally cheaper subproblems for lower and upper bounding. To further accelerate convergence, we derive envelopes of common covariance functions for GPs and tight relaxations of acquisition functions used in Bayesian optimization including expected improvement, probability of improvement, and lower confidence bound. In total, we reduce computational time by orders of magnitude compared to state-of-the-art methods, thus overcoming previous computational burdens. We demonstrate the performance and scaling of the proposed method and apply it to Bayesian optimization with global optimization of the acquisition function and chance-constrained programming. The Gaussian process models, acquisition functions, and training scripts are available open-source within the “MeLOn—Machine Learning Models for Optimization” toolbox
(https://git.rwth-aachen.de/avt.svt/public/MeLOn).
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 3, September 2021
An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
Fei Li, Zheng Qu
We propose an inexact proximal augmented Lagrangian framework with explicit inner problem termination rule for composite convex optimization problems. We consider arbitrary linearly convergent inner solver including in particular stochastic algorithms, making the resulting framework more scalable facing the ever-increasing problem dimension. Each subproblem is solved inexactly with an explicit and self-adaptive stopping criterion, without requiring to set an a priori target accuracy. When the primal and dual domain are bounded, our method achieves O(1/ϵ√) and O(1/ϵ) complexity bound in terms of number of inner solver iterations, respectively for the strongly convex and non-strongly convex case. Without the boundedness assumption, only logarithm terms need to be added and the above two complexity bounds increase respectively to O~(1/ϵ√) and O~(1/ϵ), which hold both for obtaining ϵ-optimal and ϵ-KKT solution. Within the general framework that we propose, we also obtain O~(1/ϵ) and O~(1/ϵ2) complexity bounds under relative smoothness assumption on the differentiable component of the objective function. We show through theoretical analysis as well as numerical experiments the computational speedup possibly achieved by the use of randomized inner solvers for large-scale problems.
Full Text: PDF
MPC 2021, ISSUE 2
Mathematical Programming Computation, Volume 13, Issue 2, June 2021
Incorporating bounds from decision diagrams into integer programming
Christian Tjandraatmadja, Willem-Jan van Hoeve
Decision diagrams have been successfully used to help solve several classes of discrete optimization problems. We explore an approach to incorporate them into integer programming solvers, motivated by the wide adoption of integer programming technology in practice. The main challenge is to map generic integer programming models to a recursive structure that is suitable for decision diagram compilation. We propose a framework that opportunistically constructs decision diagrams for suitable substructures, if present. In particular, we explore the use of a prevalent substructure in integer programming solvers known as the conflict graph, which we show to be amenable to decision diagrams. We use Lagrangian relaxation and constraint propagation to consider constraints that are not represented directly by the substructure. We use the decision diagrams to generate dual and primal bounds to improve the pruning process of the branch-and-bound tree of the solver. Computational results on the independent set problem with side constraints indicate that our approach can provide substantial speedups when conflict graphs are present.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 2, June 2021
Signomial and polynomial optimization via relative entropy and partial dualization
Riley Murray, Venkat Chandrasekaran, Adam Wierman
We describe a generalization of the Sums-of-AM/GM-Exponential (SAGE) methodology for relative entropy relaxations of constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE certificates conveniently and transparently blend with convex duality, in a way which enables partial dualization of certain structured constraints. This more general approach retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), and inspires a projective method of solution recovery which respects partial dualization. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package.
Full Text: PDF.
A Publisher Correction to this article was published on 09 February 2021
Mathematical Programming Computation, Volume 13, Issue 2, June 2021
Publisher Correction to: Signomial and polynomial optimization via relative entropy and partial dualization
Riley Murray, Venkat Chandrasekaran, Adam Wierman
In the original publication of the article, the reference list in the pdf version has been published with an error. The correct reference list is given in this correction.
The original article has been updated.
Full Text: PDF
AuthorsMathematical Programming Computation, Volume 13, Issue 2, June 2021
Minotaur: a mixed-integer nonlinear optimization toolkit
Ashutosh Mahajan, Sven Leyffer, Todd Munson, Jeff Linderoth, James Luedtke, Todd Munson
We present a flexible framework for general mixed-integer nonlinear programming (MINLP), called Minotaur, that enables both algorithm exploration and structure exploitation without compromising computational efficiency. This paper documents the concepts and classes in our framework and shows that our implementations of standard MINLP techniques are efficient compared with other state-of-the-art solvers. We then describe structure-exploiting extensions that we implement in our framework and demonstrate their impact on solution times. Without a flexible framework that enables structure exploitation, finding global solutions to difficult nonconvex MINLP problems will remain out of reach for many applications.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 2, June 2021
Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
Krešimir Mihić, Mingxi Zhu, Yinyu Ye
The Alternating Direction Method of Multipliers (ADMM) has gained a lot of attention for solving large-scale and objective-separable constrained optimization. However, the two-block variable structure of the ADMM still limits the practical computational efficiency of the method, because one big matrix factorization is needed at least once even for linear and convex quadratic programming. This drawback may be overcome by enforcing a multi-block structure of the decision variables in the original optimization problem. Unfortunately, the multi-block ADMM, with more than two blocks, is not guaranteed to be convergent. On the other hand, two positive developments have been made: first, if in each cyclic loop one randomly permutes the updating order of the multiple blocks, then the method converges in expectation for solving any system of linear equations with any number of blocks. Secondly, such a randomly permuted ADMM also works for equality-constrained convex quadratic programming even when the objective function is not separable. The goal of this paper is twofold. First, we add more randomness into the ADMM by developing a randomly assembled cyclic ADMM (RAC-ADMM) where the decision variables in each block are randomly assembled. We discuss the theoretical properties of RAC-ADMM and show when random assembling helps and when it hurts, and develop a criterion to guarantee that it converges almost surely. Secondly, using the theoretical guidance on RAC-ADMM, we conduct multiple numerical tests on solving both randomly generated and large-scale benchmark quadratic optimization problems, which include continuous, and binary graph-partition and quadratic assignment, and selected machine learning problems. Our numerical tests show that the RAC-ADMM, with a variable-grouping strategy, could significantly improve the computation efficiency on solving most quadratic optimization problems.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 2, June 2021
Polytope volume by descent in the face lattice and applications in social choice
Winfried Bruns, Bogdan Ichim
We describe the computation of polytope volumes by descent in the face lattice, its implementation in Normaliz, and the connection to reverse-lexicographic triangulations. The efficiency of the algorithm is demonstrated by several high dimensional polytopes of different characteristics. Finally, we present an application to voting theory where polytope volumes appear as probabilities of certain paradoxa.
Full Text: PDF
MPC 2021, ISSUE 1
Mathematical Programming Computation, Volume 13, Issue 1, March 2021
Asynchronous Lagrangian scenario decomposition
Ignacio Aravena, Anthony Papavasiliou
We present a distributed asynchronous algorithm for solving two-stage stochastic mixed-integer programs (SMIP) using scenario decomposition, aimed at industrial-scale instances of the stochastic unit commitment (SUC) problem. The algorithm is motivated by large differences in run times observed among scenario subproblems of SUC instances, which can result in inefficient use of distributed computing resources by synchronous parallel algorithms. Our algorithm performs dual iterations asynchronously using a block-coordinate subgradient descent method which allows performing block-coordinate updates using delayed information, while candidate primal solutions are recovered from the solutions of scenario subproblems using heuristics. We present a high performance computing implementation of the asynchronous algorithm, detailing the operations performed by each parallel process and the communication mechanisms among them. We conduct numerical experiments using SUC instances of the Western Electricity Coordinating Council system with up to 1000 scenarios and of the Central Western European system with up to 120 scenarios. We also conduct numerical experiments on generic SMIP instances from the SIPLIB library (DCAP and SSLP). The results demonstrate the general applicability of the proposed algorithm and its ability to solve industrial-scale SUC instances within operationally acceptable time frames. Moreover, we find that an equivalent synchronous parallel algorithm would leave cores idle up to 80.4% of the time on our realistic test instances, an observation which underscores the need for designing asynchronous optimization schemes in order to fully exploit distributed computing on real world applications.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 1, March 2021
Hard to solve instances of the Euclidean Traveling Salesman Problem
Stefan Hougardy, Xianghui Zhong
The well known 4/3 conjecture states that the integrality ratio of the subtour LP is at most 4/3 for metric Traveling Salesman instances. We present a family of Euclidean Traveling Salesman instances for which we prove that the integrality ratio of the subtour LP converges to 4/3. These instances (using the rounded Euclidean norm) turn out to be hard to solve exactly with Concorde, the fastest existing exact TSP solver. For a 200 vertex instance from our family of Euclidean Traveling Salesman instances Concorde needs several days of CPU time. This is more than 1,000,000 times more runtime than for a TSPLIB instance of similar size. Thus our new family of Euclidean Traveling Salesman instances may serve as new benchmark instances for TSP algorithms.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 1, March 2021
Mixed-integer programming techniques for the connected max-k-cut problem
Christopher Hojny, Imke Joormann, Hendrik Lüthen, Martin Schmidt
We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 1, March 2021
MiniCP: a lightweight solver for constraint programming
L. Michel, P. Schaus, P. Van Hentenryck
This paper introduces MiniCP, a lightweight, open-source solver for constraint programming. MiniCP is motivated by educational purposes and the desire to provide the core implementation of a constraint-programming solver for students in computer science and industrial engineering. The design of MiniCP provides a one-to-one mapping between the theoretical and implementation concepts and its compositional abstractions favor extensibility and flexibility. MiniCP obviously does not support all available constraint-programming features and implementation techniques, but these could be implemented as future extensions or exploratory projects. MiniCP also comes with a full set of exercises, unit tests, and development projects.
Full Text: PDF
Mathematical Programming Computation, Volume 13, Issue 1, March 2021
A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
Daniel Blado, Alejandro Toriello
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We propose an exact algorithm based on a reformulation of the value function linear program, which dynamically prices variables to refine a value function approximation and generates cutting planes to maintain a dual bound. We provide a detailed analysis of the zero-capacity case, in which the knapsack capacity is zero, and all item sizes have positive probability of equaling zero. We also provide theoretical properties of the general algorithm and an extensive computational study. Our main empirical conclusion is that the algorithm is able to significantly reduce the gap when initial bounds and/or heuristic policies perform poorly.
Full Text: PDF
MPC 2020, ISSUE 4
Mathematical Programming Computation, Volume 12, Issue 4, December 2020
A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
Sahar Tahernejad, Ted K. Ralphs, Scott T. DeNegre
In this paper, we describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) using a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range of bilevel optimization problems. The framework has been fully implemented in the open-source solver MibS. The paper describes the algorithmic options offered by MibS and presents computational results evaluating the effectiveness of the various options for the solution of a number of classes of bilevel optimization problems from the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2020
A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
Shujun Bi, Shaohua Pan, Defeng Sun
This paper concerns with a noisy structured low-rank matrix recovery problem which can be
modeled as a structured rank minimization problem. We reformulate this problem as a mathematical
program with a generalized complementarity constraint (MPGCC), and show that its penalty version,
yielded by moving the generalized complementarity constraint to the objective, has the same global
optimal solution set as the MPGCC does whenever the penalty parameter is over a certain threshold.
Then, by solving the exact penalty problem in an alternating way, we obtain a multi-stage convex
relaxation approach. We provide theoretical guarantees for our approach under a mild restricted
eigenvalue condition, by quantifying the reduction of the error and approximate rank bounds of
the first stage convex relaxation in the subsequent stages and establishing the geometric
convergence of the error sequence in a statistical sense. Numerical experiments are conducted
for some structured low-rank matrix recovery examples to confirm our theoretical findings.
Our code can be achieved from https://doi.org/10.5281/zenodo.3600639.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2020
Implementation of an interior point method with basis preconditioning
Lukas Schork, Jacek Gondzio
The implementation of a linear programming interior point solver is described that is based on iterative linear algebra. The linear systems are preconditioned by a basis matrix, which is updated from one interior point iteration to the next to bound the entries in a certain tableau matrix. The update scheme is based on simplex-type pivot operations and is implemented using linear algebra techniques from the revised simplex method. An initial basis is constructed by a crash procedure after a few interior point iterations. The basis at the end of the interior point solve provides the starting basis for a crossover method which recovers a basic solution to the linear program. Results of a computational study on a diverse set of medium to large-scale problems are discussed.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2020
OSQP: an operator splitting solver for quadratic programs
Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, Stephen Boyd
We present a general-purpose solver for convex quadratic programs based on the alternating direction method of multipliers, employing a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix at almost every iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. It can be configured to be division-free once an initial matrix factorization is carried out, making it suitable for real-time applications in embedded systems. In addition, our technique is the first operator splitting method for quadratic programs able to reliably detect primal and dual infeasible problems from the algorithm iterates. The method also supports factorization caching and warm starting, making it particularly efficient when solving parametrized problems arising in finance, control, and machine learning. Our open-source C implementation OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. It is typically ten times faster than competing interior-point methods, and sometimes much more when factorization caching or warm start is used. OSQP has already shown a large impact with tens of thousands of users both in academia and in large corporations.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 4, December 2020
An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems with integer variables
Giampaolo Liuzzi, Stefano Lucidi, Francesco Rinaldi
In this paper, we develop a new algorithmic framework to solve black-box problems with integer variables. The strategy included in the framework makes use of specific search directions (so called primitive directions) and a suitably developed nonmonotone line search, thus guaranteeing a high level of freedom when exploring the integer lattice. First, we describe and analyze a version of the algorithm that tackles problems with only bound constraints on the variables. Then, we combine it with a penalty approach in order to solve problems with simulation constraints. In both cases we prove finite convergence to a suitably defined local minimum of the problem. We report extensive numerical experiments based on a test bed of both bound-constrained and generally-constrained problems. We show the effectiveness of the method when compared to other state-of-the-art solvers for black-box integer optimization.
Full Text: PDF
MPC 2020, ISSUE 3
Mathematical Programming Computation, Volume 12, Issue 3, September 2020
Robust Euclidean embedding via EDM optimization
Shenglong Zhou, Naihua Xiu, Hou-Duo Qi
This paper aims to propose an efficient numerical method for the most challenging problem known as the robust Euclidean embedding (REE) in the family of multi-dimensional scaling (MDS). The problem is notoriously known to be nonsmooth, nonconvex and its objective is non-Lipschitzian. We first explain that the semidefinite programming (SDP) relaxations and Euclidean distance matrix (EDM) approach, popular for other types of problems in the MDS family, failed to provide a viable method for this problem. We then propose a penalized REE (PREE), which can be economically majorized. We show that the majorized problem is convex provided that the penalty parameter is above certain threshold. Moreover, it has a closed-form solution, resulting in an efficient algorithm dubbed as PREEEDM (for Penalized REE via EDM optimization). We prove among others that PREEEDM converges to a stationary point of PREE, which is also an approximate critical point of REE. Finally, the efficiency of PREEEDM is compared with several state-of-the-art methods including SDP and EDM solvers on a large number of test problems from sensor network localization and molecular conformation.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 3, September 2020
Generation techniques for linear programming instances with controllable properties
Simon Bowly, Kate Smith-Miles, Davaatseren Baatar, Hans Mittelmann
This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable of generating any feasible bounded linear program, and that parameterised generators and search algorithms using this approach generate only feasible bounded instances. Our results demonstrate that controlled generation and instance space search using this method achieves feature diversity more effectively than using a direct representation.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 3, September 2020
A rotation-based branch-and-price approach for the nurse scheduling problem
Antoine Legrain, Jérémy Omer, Samuel Rosat
In this paper, we describe an algorithm for the personalized nurse scheduling problem. We focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition. One specificity of this version is that most constraints are soft, meaning that they can be violated at the price of a penalty. We model the problem as an integer program (IP) that we solve using a branch-and-price procedure. This model is, to the best of our knowledge, comparable to no other from the literature, since each column of the IP corresponds to a rotation, i.e., a sequence of consecutive worked days for a nurse. In contrast, classical models involve individual nurse schedules over the complete horizon. We tackle instances involving up to 120 nurses and 4 shifts over an 8-weeks horizon by embedding the branch-and-price in a large-neighborhood-search framework. Initial solutions of the large-neighborhood search are found by a rolling-horizon algorithm well-suited to the rotation model.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 3, September 2020
An adaptive primal-dual framework for nonsmooth convex minimization
Quoc Tran-Dinh, Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher
We propose a new self-adaptive and double-loop smoothing algorithm to solve composite,
nonsmooth, and constrained convex optimization problems. Our algorithm is based on
Nesterov’s smoothing technique via general Bregman distance functions. It self-adaptively
selects the number of iterations in the inner loop to achieve a desired complexity bound
without requiring to set the accuracy a priori as in variants of augmented Lagrangian
methods (ALM). We prove O(1/k)-convergence rate on the last iterate of the outer sequence
for both unconstrained and constrained settings in contrast to ergodic rates which are c
ommon in ALM as well as alternating direction method-of-multipliers literature.
Compared to existing inexact ALM or quadratic penalty methods, our analysis does not rely
on the worst-case bounds of the subproblem solved by the inner loop. Therefore, our
algorithm can be viewed as a restarting technique applied to the ASGARD method in
Tran-Dinh et al. (SIAM J Optim 28(1):96–134, 2018) but with rigorous theoretical
guarantees or as an inexact ALM with explicit inner loop termination rules and
adaptive parameters. Our algorithm only requires to initialize the parameters once,
and automatically updates them during the iteration process without tuning.
We illustrate the superiority of our methods via several examples as compared
to the state-of-the-art.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 3, September 2020
Parsimonious formulations for low-diameter clusters
Hosseinali Salemi, Austin Buchanan
In the analysis of networks, one often searches for tightly knit clusters. One property of a “good” cluster is a small diameter (say, bounded by k), which leads to the concept of a k-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or dominate several previously existing formulations. Our best-performing formulation uses only node variables (quite unlike previous formulations) and imposes the diameter-at-most-k constraints via an exponentially large class of cut-like inequalities. A relatively simple implementation of the cut-like formulation easily outperforms previous approaches, solving dozens of instances of the maximum k-club problem in a second or two that would take hours by other formulations. Moreover, the cut-like formulation is more general in the sense that it applies even when distances are not measured in terms of hops. While we consider only the k-club problem in this paper, the proposed techniques may also be useful in other applications where compact solutions are key (e.g., political districting and wildlife reserve design).
Full Text: PDF
MPC 2020, ISSUE 2
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
Special issue forward: the 2018 Mixed Integer Programming workshop
Daniel Bienstock, Giacomo Nannicini
The 2018 Mixed Integer Programming workshop took place at Clemson University (Greenville, South Carolina) June 18–21.
The goal of the MIP workshop series is to discuss recent research in Mixed Integer Programming, and the 2018 edition consisted
of a single track of 20 invited talks, together with a poster session with 26 posters.
The six papers published in this special volume are related to talks presented at the workshop.
All the papers underwent a rigorous peer-review process; we are very grateful to the anonymous referees,
and to the guest editors who handled the submissions for this special issue (Claudia D’Ambrosio,
Marcos Goycoolea, Oktay Gunluk, Jim Luedtke, Michele Monaci, Jean-Philippe Richard).
We are also grateful to the local organization committee (Akshay Gupte, Matthew Saltzman, Cole Smith) for making this workshop possible.
On behalf of the program committee (Philipp Christophel, Simge Küçükyavuz, Ruth Misener, Giacomo Nannicini, Alejandro Toriello).
Daniel Bienstock and Giacomo Nannicini, New York, May 2020.
On behalf of the program committee (Philipp Christophel, Simge Küçükyavuz, Ruth Misener, Giacomo Nannicini, Alejandro Toriello).
Daniel Bienstock and Giacomo Nannicini, New York, May 2020.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
On integer and bilevel formulations for the k-vertex cut problem
Fabio Furini, Ivana Ljubić, Enrico Malaguti, Paolo Paronuzzi
The family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
On the impact of running intersection inequalities for globally solving polynomial optimization problems
Alberto Del Pia, Aida Khajavirad, Nikolaos V. Sahinidis
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations of the form ze=∏v∈ezv, e∈E, where E denotes a set of subsets of cardinality at least two of a ground set. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
K-adaptability in two-stage mixed-integer robust optimization
Anirudh Subramanyam, Chrysanthos E. Gounaris, Wolfram Wiesemann
We study two-stage robust optimization problems with mixed discrete-continuous decisions in both stages. Despite their broad range of applications, these problems pose two fundamental challenges: (i) they constitute infinite-dimensional problems that require a finite-dimensional approximation, and (ii) the presence of discrete recourse decisions typically prohibits duality-based solution schemes. We address the first challenge by studying a K-adaptability formulation that selects K candidate recourse policies before observing the realization of the uncertain parameters and that implements the best of these policies after the realization is known. We address the second challenge through a branch-and-bound scheme that enjoys asymptotic convergence in general and finite convergence under specific conditions. We illustrate the performance of our algorithm in numerical experiments involving benchmark data from several application domains.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
A novel matching formulation for startup costs in unit commitment
Bernard Knueven, James Ostrowski, Jean-Paul Watson
We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both our proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. Our proposed formulation is tested empirically against existing formulations on large-scale UC instances drawn from real-world data. While requiring more variables than the current state-of-the-art formulation, our proposed formulation requires fewer constraints, and is empirically demonstrated to be as tight as a perfect formulation for startup costs. This tightening can reduce the computational burden in comparison to existing formulations, especially for UC instances with large reserve margins and high penetration levels of renewables.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
Outer approximation with conic certificates for mixed-integer convex problems
Chris Coey, Miles Lubin, Juan Pablo Vielma
A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with K∗cuts derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all subproblems are well-posed, the algorithm detects infeasibility or unboundedness or returns an optimal solution in finite time. Using properties of the conic certificates, we show that the K∗ cuts imply certain practically-relevant guarantees about the quality of the polyhedral relaxations, and demonstrate how to maintain helpful guarantees when the LP solver uses a positive feasibility tolerance. We discuss how to disaggregateK∗ cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful K∗ cuts. Our new open source MI-conic solver Pajarito (github.com/JuliaOpt/Pajarito.jl) uses an external mixed-integer linear solver to manage the search tree and an external continuous conic solver for subproblems. Benchmarking on a library of mixed-integer second-order cone (MISOCP) problems, we find that Pajarito greatly outperforms Bonmin (the leading open source alternative) and is competitive with CPLEX’s specialized MISOCP algorithm. We demonstrate the robustness of Pajarito by solving diverse MI-conic problems involving mixtures of positive semidefinite, second-order, and exponential cones, and provide evidence for the practical value of our analyses and enhancements of K∗ cuts.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 2, June 2020
Split cuts from sparse disjunctions
Ricardo Fukasawa, Laurent Poirrier, Shenghao Yang
Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the strength of split cuts that exploit sparsity. In particular, we show that restricting ourselves to sparse disjunctions—and furthermore, ones that have small disjunctive coefficients—still leads to a significant portion of the total gap closed with arbitrary split cuts. We also show how to exploit sparsity structure that is implicit in the MIP formulation to produce splits that are sparse yet still effective. Our results indicate that one possibility to produce good split cuts is to try and exploit such structure.
Full Text: PDF
MPC 2020, ISSUE 1
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
A hybrid quasi-Newton projected-gradient method with application to Lasso and basis-pursuit 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 projected-gradient method with limited-memory 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 basis-pursuit denoise problem through the root-finding 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 bound-constrained problems as well as problems restricted to the simplex.
Full Text: PDF
Mathematical Programming Computation, Volume 12, Issue 1, March 2020
A branch-and-price algorithm for capacitated hypergraph vertex separation
Michael Bastubbe, Marco E. Lübbecke
We exactly solve the NP-hard 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 branch-and-price. 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 re-arranging a matrix into single-bordered block-diagonal 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 COIN-OR 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 k-partition problem
Guanglei Wang, Hassan Hijazi
The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut 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 state-of-the-art.
Full Text: PDF
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
MPC 2018, ISSUE 4
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Cubic regularization in symmetric rank-1 quasi-Newton methods
Hande Y. Benson, David F. Shanno
Quasi-Newton methods based on the symmetric rank-one (SR1) update have been known to be fast and provide better approximations of the true Hessian than popular rank-two 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 n-step 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 2000-study, 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 2000-study. 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 semi-proximal 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 semi-proximal terms for solving a class of convex composite conic optimization problems, of which some are high-dimensional, to moderate accuracy. Our primary motivation is that this method, together with properly chosen semi-proximal 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 non-negative semidefinite programming problems, with or without inequality constraints, are conducted. The corresponding results showed that all these multi-block 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 SOCP-based spatial branch-and-cut 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 non-convex program, presents a major computational challenge to today’s power industry for the real-time operation of large-scale power grids. In this paper, we propose a new technique for reformulation of the rank constraints using both principal and non-principal 2-by-2 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 four-cycles in the power network. We study second-order 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 SOCP-based spatial branch-and-cut method to obtain the global optimum of AC OPF. Extensive computational experiments show that the proposed algorithm significantly outperforms the state-of-the-art SDP-based 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 open-source library for black-box optimization with costly function evaluations
Alberto Costa, Giacomo Nannicini
We consider the problem of optimizing an unknown function given as an oracle over a mixed-integer box-constrained 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 black-box optimization problem with costly evaluation. This paper describes the solution methodology implemented in the open-source library RBFOpt, available on COIN-OR. 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 mixed-integer nonlinear unconstrained problems taken from the literature: it outperforms the open-source 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 NP-hard 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 IF-THEN 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 user-defined constraints. This method is useful for producing non-black-box predictive models, and has the benefit of a clear user-defined 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 two-phase augmented Lagrangian method for convex quadratic semidefinite programming
Xudong Li, Defeng Sun, Kim-Chuan Toh
In this paper, we present a two-phase 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 QSDPNAL-Phase 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 QSDPNAL-Phase 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 two-phase 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, high-quality 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 odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based 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 mixed-integer 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 fail-safe techniques, convexity identification at each node of the branch-and-bound 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 widely-used 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 one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic 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 two-row 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 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (Z × Z + )-free sets corresponding to facet-defining 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 so-called trivial fill-in function to exploit the integrality of more non-basic 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 branch-and-bound 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 branch-and-bound 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, Jean-Paul Watson, Victor M. Zavala, Lorenz T. Biegler
We describe pyomo.dae, an open source Python-based modeling framework that enables high-level 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 high-order differential equations and partial differential equations, defined on restricted domain types, and the ability to automatically trans- form high-level abstract models into finite-dimensional algebraic problems that can be solved with off-the-shelf 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 state-of-the-art 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 mixed-integer programs
Kibaek Kim, Victor M. Zavala
We present algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide an open-source software implementation that we call DSP. Our innovations include the incorporation of Benders-like cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible first-stage solutions for problems without (relative) complete recourse. We also use an interior-point 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 lrslib-062.tar.gz which has MD5 hash be5da7b3b90cc2be628dcade90c5d 1b9.
Full Text: PDF
MPC 2018, ISSUE 1
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
Tillmann Weisser, Jean B. Lasserre, Kim-Chuan 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 Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem.Moreover, for the class of SOS-convex 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
Branch-and-cut 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 branch-and-cut 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 recently-proposed fast local searches. We also propose a fast implementation of a well-known 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 branch-and-bound 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 open-source 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 branch-and-bound 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 branch-and-bound 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
Lift-and-project cuts for convex mixed integer nonlinear programs
Mustafa R. Kilinc, Jeff Linderoth, James Luedtke
We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project 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 branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances.We also demonstrate that combining lift-and-project 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, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer 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 Newton-type 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 open-source 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 general-purpose 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 large-scale 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 fine-tune the many algorithmic parameters of the resulting large class of SM, and we test them on two different LDs of the Fixed-Charge 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 mixed-integer 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 mixed-integer 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 state-of-the-art 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 LP-based 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 Ben-Tal 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 formulation-based algorithms forMICQP.We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement 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 computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem
Matthias Köppe, Yuan Zhou
We describe new computer-based 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 goal-oriented Steiner tree algorithm
Stefan Hougardy, Jannik Silvanus, Jens Vygen
We present a new exact algorithm for the Steiner tree problem in edge-weighted 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 well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case 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 d-dimensional 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 node-based 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 NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut 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 over-modeling, 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 node-based model and the previous state-of-the-art 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
SCIP-Jack—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 problem-specific. In contrast, this paper introduces a general-purpose 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 state-of-the-art MIP-framework. The result is a high-performance 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
Swap-vertex based neighborhood for Steiner tree problems
Zhang-Hua Fu, Jin-Kao Hao
Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex 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 swap-vertex 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 swap-vertex moves. Additionally, in order to discriminate different swap-vertex 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 swap-vertex 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 three-index 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 well-known separation algorithms exploit the sparsity of x, we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index 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 k-index 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 branch-cut-and-price 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 branch-cut-and-price 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 limited-memory and trust-region techniques
Oleg Burdakov, Lujin Gong, Spartak Zikrin, Ya-xiang Yuan
Limited-memory quasi-Newton methods and trust-region 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 large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.
Full Text: PDF
MPC 2016, ISSUE 4
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
Customizing the solution process of COIN-OR’s linear solvers with Python
Mehdi Towhidi, Dominique Orban
Implementations of the simplex method differ mostly in specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer program- ming differ mostly in the type of cuts and the exploration of the search tree. We provide a scripting mechanism to easily implement and experiment with primal and dual pivot rules for the simplex method, by building upon COIN-OR’s open-source linear programming package CLP, without explicitly interacting with the underlying C++ layers of CLP. In the same manner, users can customize the solution process of mixed-integer linear programs using the CBC and CGL COIN-OR packages by cod- ing branch-and-cut strategies and cut generators in Python. The Cython programming language ensures communication between Python and C++ libraries and activates user-defined customizations as callbacks. Our goal is to emphasize the ease of devel- opment in Python while maintaining acceptable performance. The resulting software, named CyLP, has become a part of COIN-OR and is available under open-source terms. For illustration, we provide an implementation of the positive edge rule—a recently proposed rule that is particularly efficient on degenerate problems—and demonstrate how to customize branch-and-cut node selection in the solution of a mixed-integer program.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
Capitalizing on live variables: new algorithms for efficient Hessian computation via automatic differentiation
Mu Wang, Assefaw Gebremedhin, Alex Pothen
Werevisitanalgorithm[calledEdgePushing(EP)]forcomputingHessians using Automatic Differentiation (AD) recently proposed by Gower and Mello (Optim Methods Softw 27(2): 233–249, 2012). Here we give a new, simpler derivation for the EP algorithm based on the notion of live variables from data-flow analysis in compiler theory and redesign the algorithm with close attention to general applicability and performance. We call this algorithm Livarh and develop an extension of Livarh that incorporates preaccumulation to further reduce execution time—the resulting algo- rithm is called Livarhacc. We engineer robust implementations for both algorithms Livarh and Livarhacc within ADOL-C, a widely-used operator overloading based AD software tool. Rigorous complexity analyses for the algorithms are provided, and the performance of the algorithms is evaluated using a mesh optimization application and several kinds of synthetic functions as testbeds. The results show that the new algo- rithms outperform state-of-the-art sparse methods (based on sparsity pattern detection, coloring, compressed matrix evaluation, and recovery) in some cases by orders of mag- nitude. We have made our implementation available online as open-source software and it will be included in a future release of ADOL-C.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix
Dennis Janka, Christian Kirches, Sebastian Sager, Andreas Wächter
We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs neces- sitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 4, November 2016
A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
Markus Sinnl, Ivana Ljubic
The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large- scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the under- lying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25.
Full Text: PDF
MPC 2016, ISSUE 3
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
Robert Vanderbei, Kevin Lin, Han Liu, Lie Wang
We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as ?1_?s and Mirror Prox regardless of the sparsity level or problem size.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
A nonmonotone GRASP
M. De Santis, P. Festa, G. Liuzzi, S. Lucidi, F. Rinaldi
A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
Phase retrieval for imaging problems
Fajwel Fogel, Irène Waldspurger, Alexandre D’Aspremont
We study convex relaxation algorithms for phase retrieval on imaging problems. We show that exploiting structural assumptions on the signal and the observations, such as sparsity, smoothness or positivity, can significantly speed-up convergence and improve recovery performance. We detail numerical results in molecular imaging experiments simulated using data from the Protein Data Bank.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 3, September 2016
RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems
Evrim Dalkiran, Hanif D. Sherali
In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.
Full Text: PDF
MPC 2016, ISSUE 2
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
A practical volume algorithm
Ben Cousins, Santosh Vempala
We present a practical algorithm for computing the volume of a convex body with a target relative accuracy parameter ?>0. The convex body is given as the intersection of an explicit set of linear inequalities and an ellipsoid. The algorithm is inspired by the volume algorithms in Lovász and Vempala (J Comput Syst Sci 72(2):392–417, 2006) and Cousins and Vempala (SODA, pp. 1215–1228, 2014), but makes significant departures to improve performance, including the use of empirical convergence tests, an adaptive annealing scheme and a new rounding algorithm. We propose a benchmark of test bodies and present a detailed evaluation of our algorithm. Our results indicate that that volume computation and integration might now be practical in moderately high dimension (a few hundred) on commodity hardware.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
Communication protocols for options and results in a distributed optimization environment
Horand Gassmann, Jun Ma, Kipp Martin
Much has been written about optimization instance formats. The MPS standard for linear mixed-integer programs is well known and has been around for many years. Other extensible formats are available for other optimization categories such as stochastic and nonlinear programming. However, the problem instance is not the only piece of information shared between the instance generator and the solver. Solver options and solver results must also be communicated. To our knowledge there is no commonly accepted format for representing either solver options or solver results. In this paper we propose a framework and theory for solver option and solver result representation in a modern distributed computing environment. A software implementation of the framework is available as an open-source COIN-OR project.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
Henrik A. Friberg
aiming to challenge commercial and open source solvers on mainstream cone support. In this paper, 121 mixed-integer and continuous second-order cone problem instances have been selected from 11 categories as representative for the instances available online. Since current file formats were found incapable, we embrace the new Conic Benchmark Format as standard for conic optimization. Tools are provided to aid integration of this format with other software packages.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
Erratum to: CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
Henrik A. Friberg
The below statement was inadvertently missed out during the typesetting process. The correct text is provided below.
In Sect. 4.1, the list of certificates a solver could return for conic continuous optimization problems is not complete as claimed, as the paper was published without the following fifth point:
In Sect. 4.1, the list of certificates a solver could return for conic continuous optimization problems is not complete as claimed, as the paper was published without the following fifth point:
- certified dual facial reducibility when we are given a feasible point to problem (P), modified such that b and B are fixed to zero, with a zero-valued objective value, cTc+<C,X>=0 (within a tolerance), and non-zero entries of any self-dual cone. This is a facial reduction certificate for (D) showing it to be ill-posed in the sense of Renegar [2].
References
- Permenter, F., Friberg, H.A., Andersen, E.D.: Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach. Technical report. http://www.optimization-online.org/DB_HTML/2015/09/5104.html (2015)
- Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5(3), 506–524 (1995)
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 2, June 2016
The L-shape search method for triobjective integer programming
Natashia Boland, Hadi Charkhgard, Martin Savelsbergh
We present a new criterion space search method, the L-shape search method, for finding all nondominated points of a triobjective integer program. The method is easy to implement, and is more efficient than existing methods. Moreover, it is intrinsically well-suited for producing high quality approximate nondominated frontiers early in the search process. An extensive computational study demonstrates its efficacy.
Full Text: PDF
MPC 2016, ISSUE 1
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
A new novel local search integer-programming-based heuristic for PCB assembly on collect-and-place machines
Anupam Seth, Diego Klabjan, Placid M. Ferreira
This paper presents the development of a novel vehicle-routing-based algorithm for optimizing component pick-up and placement on a collect-and-place type machine in printed circuit board manufacturing. We present a two-phase heuristic that produces solutions of remarkable quality with respect to other known approaches in a reasonable amount of computational time. In the first phase, a construction procedure is used combining greedy aspects and solutions to subproblems modeled as a generalized traveling salesman problem and quadratic assignment problem. In the second phase, this initial solution is refined through an iterative framework requiring an integer programming step. A detailed description of the heuristic is provided and extensive computational results are presented.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Large-scale optimization with the primal-dual column generation method
Jacek Gondzio, Pablo González-Brevis, Pedro Munari
The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Minimizing the sum of many rational functions
Florian Bugarin, Didier Henrion, Jean Bernard Lasserre
We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be relatively large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how public-domain software can be used to model and solve such problems. Finally, we also compare with the epigraph approach and the BARON software.
Full Text: PDF
Mathematical Programming Computation, Volume 8, Issue 1, March 2016
Improving branch-and-cut performance by random sampling
Matteo Fischetti, Andrea Lodi, Michele Monaci, Domenico Salvagnin, Andrea Tramontani
We discuss the variability in the performance of multiple runs of branch-and-cut mixed integer linear programming solvers, and we concentrate on the one deriving from the use of different optimal bases of the linear programming relaxations. We propose a new algorithm exploiting more than one of those bases and we show that different versions of the algorithm can be used to stabilize and improve the performance of the solver.
Full Text: PDF
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 real-world 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 quasi-Newton 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 object-oriented framework for scalable parallel branch and bound
Jonathan Eckstein, William E. Hart, Cynthia A. Phillips
Parallel Enumeration and Branch-and-Bound Library (PEBBL) is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms on MPI-based message-passing distributed-memory 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 two-level load balancing architecture and its support for a synchronously parallel ramp-up 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 branch-and-bound 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 mean-risk stochastic linear programs
Lewis Ntaimo, Tanisha G. Cotton
Mean-risk 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 mean-risk two-stage 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 mean-risk measures; analyzing how the instance solutions vary across different levels of risk; and understanding when it is appropriate to use a given mean-risk measure. Aggregated optimality cut and separate cut subgradient-based algorithms were implemented for each mean-risk 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 risk-neutral approach is still appropriate for most of the standard stochastic programming test instances due to their uniform or normal-like marginal distributions. However, when the distributions are modified, the risk-neutral approach may no longer be appropriate and the risk-averse approach becomes necessary. The results also show that ASD is a more conservative mean-risk 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 n2 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 (E-GTSP) 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 E-GTSP 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 state-of-the art TSP solver Lin–Kernighan–Helsgaun (LKH) on transformed E-GTSP instances. Although LKH is used without any modifications, the computational evaluation shows that all instances in a well-known 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 very-large-scale 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 E-GTSP instances. The program is free of charge for academic and non-commercial 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 block-bandedness similarly to an interior-point method. Still, the proposed method features warmstarting capabilities of active-set 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 open-source implementation qpDUNES shows that the algorithm outperforms both well-established general purpose QP solvers as well as state-of-the-art 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 Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
Kim-Chuan Toh, Liuqin Yang, Defeng Sun
In this paper, we present a majorized semismooth Newton-CG 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 3-block 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 two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE 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 2EBD-HPE 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 rank-1 tensor approximation problems constructed by Nie and Wang (SIAM J Matrix Anal Appl 35:1155–1179, 2014). The largest rank-1 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 multi-row models
Quentin Louveaux, Laurent Poirrier, Domenico Salvagnin
We develop a method for computing facet-defining valid inequalities for any mixed-integer set PJ . While our practical implementation does not return only facet-defining inequalities, it is able to find a separating cut whenever one exists. The separator is not comparable in speed with the specific cutting-plane generators used in branch-and-cut solvers, but it is general-purpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixed-integer 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 multi-row relaxations. In particular, we presentresults with four different strengthenings of the two-row intersection cut model, and multi-row models with up to fifteen rows. We conclude that only fully-strengthened two-row cuts seem to offer a significant advantage over two-row 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 fine-grained 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 3-dimensional assignment problem
Hans D. Mittelmann, Domenico Salvagnin
We address the solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digitalwireless communications.The paper describes the techniques developed to solve this instance to optimality, from the choice of an appropriate mixed-integer 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 general-purpose 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 lower-dimensional 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 branch-and-reduce 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
Multi-waydataarisesinmanyapplicationssuchaselectroencephalography 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 multi-way 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. Per-iteration 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 state-of-the-art 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 second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equality-constrained 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 working-set 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 so-called 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 active-set 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 active-set 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 a-priori information can be used to speed-up the QP solution or where high solution accuracy is required. In this paper we describe the open-source C++ software package qpOASES,which implements a parametric active-setmethod in a reliable and efficient way. Numerical tests show that qpOASES can outperform other popular academic and commercial QP solvers on small- to medium-scale convex test examples of theMaros-Mészáros QP collection. Moreover, various interfaces to third-party 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
Branch-and-cut for complementarity-constrained optimization
Ismael R. de Farias Jr., Ernee Kozyreff, Ming Zhao
We report and analyze the results of our computational testing of branch-and-cut for the complementarity-constrained 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 level-d 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 symmetry-breaking 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 branch-and-bound 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 primal-dual 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 branch-and-bound 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 branch-and-bound nodes: decision-variable 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, Kien-Cong Dang, Dominique Orban
Opal is a general-purpose system for modeling and solving algorithm optimization problems. Opal takes an algorithm as input, and as output it suggests parameter values that maximize some user-defined 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 state-of-the-art 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, Kim-Chuan 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 non-degeneracy condition, together with the strong semismoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank 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 first-order block-decomposition method for solving two-easy-block structured semidefinite programs
Renato D. C. Monteiro, Camilo Ortiz, Benar F. Svaiter
In this paper, we consider a first-order block-decomposition 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 graph-related conic SDP problems auto- matically possess the above two-easy-block structure, namely: SDPs for O-functions 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 large-scale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a Newton-CG 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 state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.
Full Text: PDF
Mathematical Programming Computation, Volume 6, Issue 2, June 2014
A branch-and-price algorithm for the multi-depot heterogeneous-fleet 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 branch-and-price 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
Matrix-free 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 first-order methods. Interior point methods (IPMs) rely on the Newton method hence they use the second-order information. They have numerous advantageous features and one clear drawback: being the second-order 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 matrix-free 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 matrix-free 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 one-dimensional signals confirms that the new approach is efficient and offers an attractive alternative to other state-of-the-art 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 sub-MINLP to explore the set of feasible roundings of an optimal solution ¯ x of a linear or nonlinear relaxation. The sub-MINLP 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 so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price 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 k-opt 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 eachsub-block 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 mixed-integer cuts are one of the key components in Branch-and-Cut solvers for mixed-integer linear programs. The textbook formula for generating these cuts is not used directly in open-source 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 mixed-integer 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 mixed-integer 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
Branch-and-cut approaches for chance-constrained 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 s-t 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 branch-and-cut 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 facet-inducing 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 branch-and-cut 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 mixed-integer 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 MUSCOD-II, a direct and simultaneous method for DAE-constrained optimal control, we demonstrate how the problem information provided by the TACO toolkit is interfaced to the solver. In addition, we show how the MS-MINTOC algorithm for mixed-integer optimal control can be used to efficiently solve mixed-integer 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 usingMUSCOD-II and MS-MINTOC inside the AMPL environment. A collection of further AMPL control models is provided on the web site http://mintoc.de. MUSCOD-II and MS-MINTOC 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 two-stage 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 high-dimensional problems in fractions of a second which permits large-scale 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 multi-threading.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 3, September 2013
A hybrid branch-and-bound approach for exact rational mixed-integer programming
William Cook, Thorsten Koch, Daniel E. Steffy, Kati Wolter
We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point 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 LP-based branch-and-bound, using numerically-safe 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 floating-point branch-and-bound 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
Trajectory-following methods for large-scale degenerate convex quadratic programming
Nicholas I. M. Gould, Dominique Orban, Daniel P. Robinson
We consider a class of infeasible, path-following 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 block-coordinate 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 step-lengths 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 state-of-the-art 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 mixed-integer programming
Vašek Chvátal, William Cook, Daniel Espinoza
A general framework for cutting-plane 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 mixed-integer programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floating-point arithmetic and in rational arithmetic.
Full Text: PDF
Mathematical Programming Computation, Volume 5, Issue 2, June 2013
Parallel stochastic gradient algorithms for large-scale matrix completion
Benjamin Recht, Christopher Ré
This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or ?2-norm. 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 speed-up nearly proportional to the number of processors. On large-scale 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 self-dual interior point method for linear and conic quadratic problems
Anders Skajaa, Erling D. Andersen, Yinyu Ye
We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual 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 black-box 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 worst-case 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 facet-defining cuts.We obtain good computational results with a branch-cut-and-price 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
Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints
I. R. de Farias Jr, E. Kozyreff, R. Gupta, M. Zhao
We report and analyze the results of our computational testing of branchand-cut 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 branch-and-cut. Finally, we report and analyze results on piecewise linear optimization problems with semi-continuous 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ópez-Negrete, 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 open-source 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 pre-factored KKT matrices and a fix-relax 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 low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
Zaiwen Wen, W. Yin, Y. Zhang
Thematrix completion problem is to recover a low-rank 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 large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (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 nuclear-norm 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
Maximum-weight 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 linear-programming column-generation technique, where variables correspond to stable sets, first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numerically-safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price 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 SQP-type algorithms for nonlinear and nonconvex mixed-integer optimization
Oliver Exler, Thomas Lehmann, Klaus Schittkowski
We present numerical results of a comparative study of codes for nonlinear and nonconvex mixed-integer optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by trust-regions, linear outer approximations, and branch-and-bound techniques. The mixed-integer quadratic programming subproblems are solved by a branch-and-cut algorithm. Second order information is updated by a quasi-Newton 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 mixed-integer test problems. Since not all of our test examples are convex, we reach the best-known 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 mixed-integer SQP code is between 240 and 500 including those needed for one- or two-sided 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 two-stage stochastic LPs with enhanced Benders decomposition
Victor Zverovich, Csaba I. Fabian, Eldon F. D. Ellison, Gautam Mitra
We report a computational study of two-stage 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 (L-shaped 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 second-stage 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 scale-up 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 branch-and-cut 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 branch-and-cut 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- and-cut 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
Jean-Paul Watson, David L. Woodruff, William E. Hart
Although stochastic programming is a powerful tool for modeling deci- sion-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists 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 mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simul- taneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source 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 multi-stage stochastic programs. By leveraging the combination of a high-level 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 lift-and-project closures
Pierre Bonami
The strengthened lift-and-project closure of a mixed integer linear pro- gram is the polyhedron obtained by intersecting all strengthened lift-and-project 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 lift-and-project 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 lift-and-project 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 penalty-interior-point algorithm for nonlinear constrained optimization
Frank E. Curtis
Penalty and interior-point 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. Interior-point methods have become the workhorse in large-scale optimization due to their New- ton-like 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 penalty-interior-point method that possesses the advantages of penalty and interior-point 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 penalty-interior-point subproblem itself, but on the design of updates for the penalty and interior-point 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
Rounding-based heuristics for nonconvex MINLPs
Giacomo Nannicini, Pietro Belotti
We propose two primal heuristics for nonconvex mixed-integer 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 mixed-integer 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 open-source 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 NP-hard 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 first-order 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 well-known 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 high-contrast 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 interior-point method for convex quadratic programs
M. P. Friedlander, D. Orban
Interior-point 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 rank-deficient Jacobians. We propose a consistent framework and accompanying theoretical justification for regularizing these linear systems. Our approach can be interpreted as a simultaneous proximal-point 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 rank-1 split cuts in mixed-integer 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 mixed-integer 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 rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Liftand-Project, 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 Branch-and-Cut 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 discrete-time 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 fill-in. 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 forMixed-Integer 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 general-purpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and Branch-and-Bound.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 first-order 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 total-variation norm, ||Wx||1 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 state-of-the-art 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 large-scale 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, Jean-Paul 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 open-source 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 full-featured 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 COIN-OR open-source 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 relax-and-cut framework for Gomory mixed-integer cuts
Matteo Fischetti, Domenico Salvagnin
Gomory mixed-integer cuts (GMICs) are widely used in modern branchand-cut codes for the solution of mixed-integer 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 rank-1 GMICs read from a basis of the original LP—the one before the addition of any cut.We adopt a relax-and-cut 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 cut-and-branch 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 (block-angular) 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 speed-up 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 mixed-integer 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 NP-hard 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 NP-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut 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 3-4
Mathematical Programming Computation, Volume 2, Issue 3-4, December 2010
Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe
We describe an implementation of nonsymmetric interior-point 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 interior-point solvers for semidefinite programming.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 3-4, 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 fixed-point 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 3-4, December 2010
A heuristic to generate rank-1 GMI cuts
Sanjeeb Dash, Marcos Goycoolea
Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer 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 rank-1 mixed-integer rounding cuts. Further, we use our heuristic to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 3-4, December 2010
Exact algorithm over an arc-time-indexed 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 medium-sized instances of the P||\sum{wj Tj} have been solved to optimality.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 3-4, December 2010
An inexact interior point method for L1-regularized sparse covariance selection
Lu Li, Kim-Chuan Toh
Sparse covariance selection problems can be formulated as logdeterminant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point 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 path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned 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 ill-conditioned 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 well-studied combinatorial optimization problem. Real-world 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, object-oriented 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 well-documented, 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 best-known solution on benchmark problems.
Full Text: PDF
Mathematical Programming Computation, Volume 2, Issue 2, June 2010
Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization
John Gunnels, Jon Lee, Susan Margulies
We provide a first demonstration of the idea that matrix-based 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 high-precision 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 MCF-separator: detecting and exploiting multi-commodity 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 multi-commodity 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 branch-and-cut 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 speeds-up 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 polyhedral-semidefinite relaxation of completely positive programs
Samuel Burer
It has recently been shown (Burer, Math Program 120:479–495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called 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 NP-hard 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 interior-point 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 box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-andbound 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 trust-region and other regularised subproblems in optimization
Nicholas I. M. Gould, Daniel P. Robinson, H. Sue Thorne
The solution of trust-region 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 high-order 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 large-scale 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 so-called 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 structure-conveying modelling language for mathematical and stochastic programming
Marco Colombo, Andreas Grothey, Jonathan Hogg, Kristian Woodsend, Jacek Gondzio
We present a structure-conveying algebraicmodelling language formathematical programming. The proposed language extends AMPL with object-oriented features that allows the user to construct models from sub-models, and is implemented as a combination of pre- and post-processing 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 decomposition-based 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
Information-based 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 branch-and-bound 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 branch-and-bound 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 2-3
Mathematical Programming Computation, Volume 1, Issue 2-3, 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 2-3, October 2009
General k-opt submoves for the Lin–Kernighan TSP heuristic
Keld Helsgaun
Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, 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. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.
Full Text: PDF
Mathematical Programming Computation, Volume 1, Issue 2-3, October 2009
Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants
Egon Balas, Pierre Bonami
Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional 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 lift-and-project (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 2-3, October 2009
Feasibility pump 2.0
Matteo Fischetti, Domenico Salvagnin
Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important NP-complete 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 diving-like 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 slowing-down 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 non-commercial 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 non-linear 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 state-of-the-art techniques for proving the validity of properties on circuits containing arithmetic.
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 non-linear 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 state-of-the-art 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 worst-case 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 mixed-integer linear programming
François Margot
In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer 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 Reduce-and-Split 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.
© 2008-2024 by Zuse Institute Berlin (ZIB).