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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7206 |
| Date | 19 July 2005 |
| Creators | Guan, Yongpei |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 659561 bytes, application/pdf |
Page generated in 0.002 seconds