On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming

• 成果类型: Article
• 署名作者: Trapp, Andrew C.; Prokopyev, Oleg A.; Schaefer, Andrew J.
• 署名单位: Worcester Polytechnic Institute; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1156
• 发表日期: 2013
• 页码: 498-511
• 关键词: decomposition; algorithm; branch; FRAMEWORK; cut

摘要

We propose a level-set approach to characterize the value function of a pure linear integer program with inequality constraints. We study theoretical properties of our characterization and show how they can be exploited to optimize a class of stochastic integer programs through a value function reformulation. Specifically, we develop algorithmic approaches that solve two-stage multidimensional knapsack problems with random budgets, yielding encouraging computational results.