Bilevel Programming and Maximally Violated Valid Inequalities

In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MIPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MIPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the prob- lem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a single-level mathematical program, yielding a stan- dard mathematical programming formulation for the separation problem. In other cases, no reformulation exists. We illustrate the principle by considering the separation problem for two well-known classes of valid inequalities