Return to search

Pairing inequalities and stochastic lot-sizing problems: A study in integer programming

Based on the recent successes in stochastic linear programming and
mixed integer programming, in this thesis we combine these two
important areas of mathematical programming; specifically we study
stochastic integer programming.

We first study a simple and important stochastic integer
programming problem, called stochastic uncapacitated lot-sizing
(SLS), which is motivated by production planning under
uncertainty. We describe a multi-stage stochastic integer
programming formulation of the problem and develop a family of
valid inequalities, called the (Q, S) inequalities. We
establish facet-defining conditions and show that these
inequalities are sufficient to describe the convex hull of
integral solutions for two-period instances. A separation
heuristic for (Q, S) inequalities is developed and
incorporated into a branch-and-cut algorithm. A computational
study verifies the usefulness of the inequalities as cuts.

Then, motivated by the polyhedral study of (Q, S)
inequalities for SLS, we analyze the underlying integer
programming scheme for general stochastic integer programming
problems. We present a scheme for generating new valid
inequalities for mixed integer programs by taking pair-wise
combinations of existing valid inequalities. The scheme is in
general sequence-dependent and therefore leads to an exponential
number of inequalities. For some special cases, we identify
combination sequences that lead to a manageable set of all
non-dominated inequalities. For the general scenario tree case, we
identify combination sequences that lead to non-dominated
inequalities. We also analyze the conditions such that the
inequalities generated by our approach are facet-defining and
describe the convex hull of integral solutions. We illustrate the
framework for some deterministic and stochastic integer programs
and we present computational results which show the efficiency of
adding the new generated inequalities as cuts.

Identiferoai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7206
Date19 July 2005
CreatorsGuan, Yongpei
PublisherGeorgia Institute of Technology
Source SetsGeorgia Tech Electronic Thesis and Dissertation Archive
Languageen_US
Detected LanguageEnglish
TypeDissertation
Format659561 bytes, application/pdf

Page generated in 0.0017 seconds