Optimization Online


A Branch-and-Cut Algorithm for Discrete Bilevel Linear Programs

Junlong Zhang(jzhang56***at***ncsu.edu)
Osman Y. Ozaltin(oyozalti***at***ncsu.edu)

Abstract: We present a branch-and-cut algorithm for solving discrete bilevel linear programs where the upper-level variables are binary and the lower-level variables are either pure integer or pure binary. This algorithm performs local search to find improved bilevel feasible solutions. We strengthen the relaxed node subproblems in the branch-and-cut search tree by generating cuts to eliminate all of the upper-level integer feasible solutions explored during the local search step. Furthermore, to avoid repeatedly solving similar bilevel integer problems in the local search, we derive structural properties of the value functions of bilevel integer programs. Most notably, we generalize the integer complementary slackness theorem to bilevel integer programs. We also propose three efficient approaches for computing the bilevel programming value functions. Our computational results show that the proposed branch-and-cut approach enhanced with the implementation of value functions and local search can solve discrete bilevel programming instances with up to 200 variables and 150 constraints in a reasonable amount of time.

Keywords: Bilevel Programming; Integer Programming; Branch and Cut; Value Functions

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

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

Citation: North Carolina State University, 05/2017

Download: [PDF]

Entry Submitted: 05/16/2017
Entry Accepted: 05/17/2017
Entry Last Modified: 05/16/2017

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 Optimization Society