This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Van Vyve, M. Search for Related Content

The Continuous Mixing Polyhedron

Center of Operations Research and Econometrics (CORE), Université catholique de Louvain, 34, Voie du Roman Pais, 1348 Louvain-la-Neuve, Belgium
vanvyve{at}core.ucl.ac.be

We analyze the polyhedral structure of the sets P^CMIX = {(s, r, z) R x R₊ⁿ x Zⁿ | s + r_j + z_j f_j, j = 1, ..., n} and P₊^CMIX = P^CMIX {s 0}. The set P₊^CMIX is a natural generalization of the mixing set studied by Pochet and Wolsey [15, 16] and Günlük and Pochet [8] and recently has been introduced by Miller and Wolsey [12]. We introduce a new class of valid inequalities that has proven to be sufficient for describing conv(P^CMIX). We give an extended formulation of size O(n) x O(n²) variables and constraints and indicate how to separate over conv(P^CMIX) in O(n³) time. Finally, we show how the mixed integer rounding (MIR) inequalities of Nemhauser and Wolsey [14] and the mixing inequalities of Günlük and Pochet [8] constitute special cases of the cycle inequalities.

Key Words: mixed integer rounding; mixing; convex hull proof; lot sizing
History: Received: October 28, 2003; revision received: May 18, 2004;revision received: August 6, 2004;

This article has been cited by other articles:

				M. Conforti, M. Di Summa, F. Eisenbrand, and L. A. Wolsey Network Formulations of Mixed-Integer Programs Mathematics of Operations Research, February 1, 2009; 34(1): 194 - 209. [Abstract] [PDF]

				M. Van Vyve Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size Mathematics of Operations Research, August 1, 2007; 32(3): 594 - 613. [Abstract] [PDF]