Optimization Online


A Branch-and-cut Algorithm for Integer Bilevel Linear Programs

Scott Denegre (sdenegre***at***lehigh.edu)
Ted Ralphs (ted***at***lehigh.edu)

Abstract: We describe a rudimentary branch-and-cut algorithm for solving integer bilevel linear programs that extends existing techniques for standard integer linear programs to this very challenging computational setting. The algorithm improves on the branch-and-bound algorithm of Moore and Bard in that it uses cutting plane techniques to produce improved bounds, does not require specialized branching strategies, and can be implemented in a straightforward way using only linear solvers. An implementation built using software components available in the COIN-OR software repository is described and preliminary computational results presented.

Keywords: Branch and cut, bilevel programming, cutting planes

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Other Topics (Game Theory )

Citation: Technical Report, COR@L Laboratory, Lehigh University (2008)

Download: [PDF]

Entry Submitted: 06/03/2008
Entry Accepted: 06/03/2008
Entry Last Modified: 09/18/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society