Integer packing sets form a well-quasi-ordering

An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y ≤ x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in … Read more

MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library

We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of 5,721 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using … Read more

Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming

The dual decomposition of stochastic mixed-integer programs can be solved by the projected subgradient algorithm. We show how to make this algorithm more amenable to parallelization in a master-worker model by describing two approaches, which can be combined in a natural way. The first approach partitions the scenarios into batches, and makes separate use of … Read more

Strong Convex Nonlinear Relaxations of the Pooling Problem

We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more

Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit

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 … Read more

Solving Box-Constrained Nonconvex Quadratic Programs

We present effective computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvatal-Gomory closure of the BQP is given by the odd-cycle inequalities even when … Read more

Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual … Read more

Valid Inequalities for Separable Concave Constraints with Indicator Variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, … Read more

High Throughput Computing for Massive Scenario Analysis and Optimization to Minimize Cascading Blackout Risk

We describe a simulation-based optimization method that allocates additional capacity to transmission lines in order to minimize the expected value of the load shed due to a cascading blackout. Estimation of the load-shed distribution is accomplished via the ORNL-PSerc-Alaska (OPA) simulation model, which solves a sequence of linear programs. Key to achieving an effective algorithm … Read more

Regularization vs. Relaxation: A convexification perspective of statistical variable selection

Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an $\ell_0$-norm penalty. Exactly enforcing the $\ell_0$-norm penalty is computationally intractable for larger scale problems, so different sparsity-inducing penalty … Read more