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

Show full item record

Please use this identifier to cite or link to this item:

Title: Pairing inequalities and stochastic lot-sizing problems: A study in integer programming
Author: Guan, Yongpei
Abstract: 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.
Type: Dissertation
Date: 2005-07-19
Publisher: Georgia Institute of Technology
Subject: Separation
Stochastic programming
Integer programming
Polyhedral study
Department: Industrial and Systems Engineering
Advisor: Committee Chair: Nemhauser, George L.; Committee Member: Ahmed, Shabbir; Committee Member: Bartholdi, John J; Committee Member: Gu, Zonghao; Committee Member: Takriti, Samer
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
guan_yongpei_200508_phd.pdf 644.1Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record