Mixed Integer Linear Programming Formulation Techniques

By Juan Pablo Vielma. 2015

379 citations recorded by the source corpus.

A wide range of problems can be modeled as Mixed Integer Linear Programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result in stronger and/or smaller formulations for a wide class of problems.

Subfields: Industrial and Manufacturing Engineering, Numerical Analysis, Organizational Behavior and Human Resource Management

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Industrial and Manufacturing Engineering

In Numerical Analysis

In Organizational Behavior and Human Resource Management

Citations in the corpus

Verifying Neural Networks with Mixed Integer Programming (2017, neutral): “ve to carry out a presolve step to determine these bounds. Determining tight bounds is critical for problem tractability: tight bounds strengthen the problem formulation and thus improve solve times (Vielma, 2015). For instance, if we can prove that the phase of a ReLU is stable, we can avoid introd”
Gas Network Optimization: A comparison of Piecewise Linear Models (2014, methodology): “As discussed in Vielma et al. (2008), 448 it seems that the reason for this functioning is more of an implementation issue 449 than a property of the SOS2 formulation. As a result, Mahlke et al. (2010) 450 develops a customized branch-and-cut algorithm able to handle more efficiently 451 SOS Type 2 ”
The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization (2015, background): “Problem (2) can be reformulated as a Mixed Integer Linear Optimization (MILO) problem — due to the major advances in algorithmic research in MILO over the past 10-15 years, these methods are widely considered as a mature technology in a subfield of mathematical programming [17], [18].”
Strong mixed-integer programming formulations for trained neural networks (2018, background): “omplete network. However, for similarly sized-formulations, combining stronger formulations (e.g. ideal instead of sharp) usually leads to complete formulations that are more computationally eﬀective [72]. Hence, our focus for all theoretical properties of the formulations will be restricted to indi”
Evaluating Robustness of Neural Networks with Mixed Integer Programming (2017, background): “Determining tight bounds is critical for problem tractability: tight bounds strengthen the problem formulation and thus improve solve times [39].”
Optimization of Tree Ensembles (2017, methodology): “This type of encoding has been used successfully in scheduling and transportation applications (so-called “by” variables, representing an event happening by some period t ; see for example Bertsimas et al. 2011); for further details, the reader is referred to Vielma (2015).”