A value-function-based exact approach for the bilevel mixed-integer programming problem

Leonardo Lozano, J. Cole Smith

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

We examine bilevel mixed-integer programs whose constraints and objective functions depend on both upper- and lower-level variables. The class of problems we consider allows for nonlinear terms to appear in both the constraints and the objective functions, requires all upper-level variables to be integer, and allows a subset of the lowerlevel variables to be integer. This class of bilevel problems is difficult to solve because the upper-level feasible region is defined in part by optimality conditions governing the lower-level variables, which are difficult to characterize because of the nonconvexity of the follower problem. We propose an exact finite algorithm for these problems based on an optimal-value-function reformulation. We demonstrate how this algorithm can be tailored to accommodate either optimistic or pessimistic assumptions on the follower behavior. Computational experiments demonstrate that our approach outperforms a state-of-the-art algorithm for solving bilevel mixed-integer linear programs.

Original languageEnglish (US)
Pages (from-to)768-786
Number of pages19
JournalOperations Research
Volume65
Issue number3
DOIs
StatePublished - May 1 2017
Externally publishedYes

Keywords

  • Bilevel optimization
  • Integer programming
  • Nonlinear programming
  • Scheduling

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A value-function-based exact approach for the bilevel mixed-integer programming problem'. Together they form a unique fingerprint.

Cite this