On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming
Andrew C. Trapp, Oleg A. Prokopyev, Andrew J. Schaefer
Operations Research · 2013 · Volume 61 · Issue 2
Abstract
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.
Keywords
integer programming, value function, characterization, level set, stochastic programming
Enable JavaScript for citation tools and additional paper interactions.