The use of linear programming duality in mixed integer programming

This paper is about the primal–dual relationship in a mixed integer programming problem (MIP) in which integer variables are binary. It shows how the primal–dual relationship of a linear programming problem (LP) can be used to advantage in MIPs. The central idea is to look conceptually at the nature of all possible LPs that arise from all possible settings for the discrete variables in order to deduce properties of the solution set. After developing the relevant theory, we show the usefulness of this approach by applying it to three totally different problems. New results are derived for the method of least median of squares in robust regression, the problem of rectilinear obnoxious-facility location, and the problem of finding a fixed-size rectangle containing the minimum weight of points.