Projection-based Reformulation and Decomposition Algorithm for A Class of Mixed-Integer Bilevel Linear Programs

Dajun Yue, Fengqi You

Research output: Chapter in Book/Report/Conference proceedingChapter

8 Scopus citations


We propose an efficient algorithm for solving mixed integer bilevel linear programs (MIBLPs). The MIBLPs addressed in this work involve continuous and integer variables in both upper- and lower-level programs. In addition, the upper-level constraints are allowed to be dependent on the lower-level solutions. We first reformulate the original MIBLP into an equivalent single-level optimization problem. The issue of relatively complete response is tackled using the disjunctive programming approach. Based on this single-level reformulation, a decomposition algorithm is developed that converges to the global optimal solution in finite iterations. The master problem provides a valid lower bound, while two subproblems are used to provide a valid upper bound or to test the feasibility. A KKT-condition-based cut is generated according to the solutions to the subproblems and added to the master problem at the end of each iteration, so that non-decreasing lower bounds can be obtained successively. An implementation of the algorithm is described and illustrative examples are presented.

Original languageEnglish (US)
Title of host publication26 European Symposium on Computer Aided Process Engineering, 2016
EditorsZdravko Kravanja, Milos Bogataj
PublisherElsevier B.V.
Number of pages6
ISBN (Print)9780444634283
StatePublished - 2016

Publication series

NameComputer Aided Chemical Engineering
ISSN (Print)1570-7946


  • decomposition
  • mixed-integer bilevel linear programming
  • reformulation

ASJC Scopus subject areas

  • General Chemical Engineering
  • Computer Science Applications


Dive into the research topics of 'Projection-based Reformulation and Decomposition Algorithm for A Class of Mixed-Integer Bilevel Linear Programs'. Together they form a unique fingerprint.

Cite this