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

6 Scopus citations

Abstract

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
PublisherElsevier B.V.
Pages481-486
Number of pages6
Volume38
ISBN (Print)9780444634283
DOIs
StatePublished - Jan 1 2016

Publication series

NameComputer Aided Chemical Engineering
Volume38
ISSN (Print)1570-7946

Keywords

  • decomposition
  • mixed-integer bilevel linear programming
  • reformulation

ASJC Scopus subject areas

  • Chemical Engineering(all)
  • Computer Science Applications

Fingerprint 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