๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

โœ Scribed by Yongpei Guan; Shabbir Ahmed; George L. Nemhauser; Andrew J. Miller

Publisher
Springer-Verlag
Year
2005
Tongue
English
Weight
334 KB
Volume
105
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical ( , S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the ( , S) inequalities to a general class of valid inequalities, called the (Q, S Q ) inequalities, and we establish necessary and sufficient conditions which guarantee that the (Q, S Q ) inequalities are facet-defining. A separation heuristic for (Q, S Q ) inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the (Q, S Q ) inequalities as cuts.

๐Ÿ“œ SIMILAR VOLUMES

A branch-and-cut algorithm for the preem
A branch-and-cut algorithm for the preemptive swapping problem
โœ Charles Bordenave; Michel Gendreau; G. Laporte ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 247 KB ๐Ÿ‘ 1 views

## Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determinin