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

• 成果类型: Article
• 署名作者: Lozano, Leonardo; Smith, J. Cole
• 署名单位: Clemson University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1589
• 发表日期: 2017
• 页码: 768-786
• 关键词: global optimization; parameter-estimation; algorithm; MODEL; optimality; formulation

摘要

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.