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

Separation;Stochastic programming;Integer programming;Lot-sizing;Polyhedral study

Guan, Yongpei ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Separation;    Stochastic programming;    Integer programming;    Lot-sizing;    Polyhedral study;   

Others  :  https://smartech.gatech.edu/bitstream/1853/7206/1/guan_yongpei_200508_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Based on the recent successes in stochastic linear programming andmixed integer programming, in this thesis we combine these twoimportant areas of mathematical programming; specifically we studystochastic integer programming.We first study a simple and important stochastic integerprogramming problem, called stochastic uncapacitated lot-sizing(SLS), which is motivated by production planning underuncertainty. We describe a multi-stage stochastic integerprogramming formulation of the problem and develop a family ofvalid inequalities, called the (Q, S) inequalities. Weestablish facet-defining conditions and show that theseinequalities are sufficient to describe the convex hull ofintegral solutions for two-period instances. A separationheuristic for (Q, S) inequalities is developed andincorporated into a branch-and-cut algorithm. A computationalstudy verifies the usefulness of the inequalities as cuts.Then, motivated by the polyhedral study of (Q, S)inequalities for SLS, we analyze the underlying integerprogramming scheme for general stochastic integer programmingproblems. We present a scheme for generating new validinequalities for mixed integer programs by taking pair-wisecombinations of existing valid inequalities. The scheme is ingeneral sequence-dependent and therefore leads to an exponentialnumber of inequalities. For some special cases, we identifycombination sequences that lead to a manageable set of allnon-dominated inequalities. For the general scenario tree case, weidentify combination sequences that lead to non-dominatedinequalities. We also analyze the conditions such that theinequalities generated by our approach are facet-defining anddescribe the convex hull of integral solutions. We illustrate theframework for some deterministic and stochastic integer programsand we present computational results which show the efficiency ofadding the new generated inequalities as cuts.