  


Bilevel Programming and the Separation Problem
Andrea Lodi (andrea.lodiunibo.it) Abstract: In recent years, branchandcut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branchandcut. This paper examines the nature of the socalled 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 problem 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 simple singlelevel mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no such polynomialsize singlelevel reformulation exists unless the polynomial hierarchy collapses to its first level (an event considered extremely unlikely in computational complexity theory). We illustrate our insights by considering the separation problem for two wellknown classes of valid inequalities. Keywords: Bilevel Programming, Cutting Planes, Separation, Computational Complexity Category 1: Integer Programming Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 03/26/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  