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
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2024 by Zuse Institute Berlin (ZIB).