A hierarchy of bounds for stochastic mixed-integer programs

Burhaneddin Sandikçi*, Nan Kong, Andrew J. Schaefer

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)

Abstract

We consider general two-stage SMIPs with recourse, in which integer variables are allowed in both stages of the problem and randomness is allowed in the objective function, the constraint matrices (i.e.; the technology matrix and the recourse matrix), and the right-hand side. We develop a hierarchy of lower and upper bounds for the optimal objective value of an SMIP by generalizing the wait-and-see solution and the expected result of using the expected value solution. These bounds become progressively stronger but generally more difficult to compute. Our numerical study indicates the bounds we develop in this paper can be strong relative to those provided by linear relaxations. Hence this new bounding approach is a complementary tool to the current bounding techniques used in solving SMIPs, particularly for large-scale and poorly formulated problems.

Original languageEnglish
Pages (from-to)253-272
Number of pages20
JournalMathematical Programming
Volume138
Issue number1-2
DOIs
Publication statusPublished - Apr 2013
Externally publishedYes

Keywords

  • Bounding
  • Mixed-integer programs
  • Stochastic programming

Fingerprint

Dive into the research topics of 'A hierarchy of bounds for stochastic mixed-integer programs'. Together they form a unique fingerprint.

Cite this