A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem

Leonardo Lozano () and J. Cole Smith ()
Additional contact information
Leonardo Lozano: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634
J. Cole Smith: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634

Operations Research, 2017, vol. 65, issue 3, 768-786

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 lower-level 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.

Keywords: bilevel optimization; integer programming; nonlinear programming; scheduling (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1589 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2017:i:3:p:768-786

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().