Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function

• 成果类型: Article
• 署名作者: Tavaslioglu, Onur; Prokopyev, Oleg A.; Schaefer, Andrew J.
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Rice University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1842
• 发表日期: 2019
• 页码: 1659-1677
• 关键词: constructive characterizations; sensitivity-analysis; DECOMPOSITION; branch; algorithm; discrete; cut; FRAMEWORK

摘要

We introduce a generalized value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. We describe its fundamental properties, which we exploit through three algorithms to calculate it. We then show how this generalized value function can be used to reformulate two classes of mixed-integer optimization problems: two-stage stochastic mixed-integer programming and multifollower bilevel mixed-integer programming. For both of these problem classes, the generalized value function approach allows the solution of instances that are significantly larger than those solved in the literature in terms of the total number of variables and number of scenarios.