A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX

We translate the algorithmic question of whether to linearize convex Mixed-Integer Quadratic Programming problems (MIQPs) into a classification task, and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in … Read more

Implementing Automatic Benders Decomposition in a Modern MIP Solver

We describe the automatic Benders decomposition implemented in the commercial solver IBM CPLEX. We propose several improvements to the state-of-the-art along two lines: making a numerically robust method able to deal with the general case and improving the efficiency of the method on models amenable to decomposition. For the former, we deal with: unboundedness, failures … Read more

Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks

Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … 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

A Note on Linear On/Off Constraints

This note studies compact representations of linear on/off constraints in mixed-integer linear optimization. A characterization of the convex hull of linear disjunctions is given in the space of original variables. This result can improve formulations of mixed-integer linear programs featuring on/off constraints by reducing the integrality gap in a Branch and Bound approach. Citation @article{, … Read more

An Outer-Inner Approximation for separable MINLPs

A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more

More Branch-and-Bound Experiments in Convex Nonlinear Integer Programming

Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a non-simplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out … Read more

An Outer-Inner Approximation for separable MINLPs

A common structure in convex mixed-integer nonlinear programs is additively separable nonlinear functions consisting of a sum of univariate functions. In the presence of such structures, we propose three improvements to the classical Outer Approximation algorithms that exploit separability. The first improvement is a simple extended formulation. The second a refined outer approximation. Finally, the … Read more

On optimizing over lift-and-project closures

The lift-and-project closure is the relaxation obtained by computing all lift-and-project cuts from the initial formulation of a mixed integer linear program or equivalently by computing all mixed integer Gomory cuts read from all tableau’s corresponding to feasible and infeasible bases. In this paper, we present an algorithm for approximating the value of the lift-and-project … Read more

Mixed Integer NonLinear Programs featuring “On/Off ” constraints: convex analysis and applications

We call ”on/off” constraint an algebraic constraint that is activated if and only if a corresponding boolean variable is turned ”on” or equal to 1. Our main subject of interest is to derive tight convex formulations of Mixed Integer NonLinear Programs (MINLPs) featuring ”on/off” constraints. We study the simple set defined by one ”on/off” constraint … Read more