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 () and Andrew J. Schaefer ()
Additional contact information
Andrew C. Trapp: School of Business, Worcester Polytechnic Institute, Worcester, Massachusetts 01609
Oleg A. Prokopyev: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Andrew J. Schaefer: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261

Operations Research, 2013, vol. 61, issue 2, 498-511

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 (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1156 (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:61:y:2013:i:2:p:498-511

Access Statistics for this article

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