Given rational numbers C_0,...,C_m and b_0,...,b_m, the mixing set with arbitrary capacities is the mixed-integer set defined by conditions s + C_t z_t  ≥ b_t , 0 ≤ t ≤ m, s ≥ 0, z_t integer, 0 ≤ t ≤ m. Such a set has applications in lot-sizing problems. We study the special case of divisible capacities, i.e. C_t /C_{t − 1} is a positive integer for 1 ≤ t ≤ m. Under this assumption, we give an extended formulation for the convex hull of the above set that uses a quadratic number of variables and constraints.

The mixing set with divisible capacities

CONFORTI, MICHELANGELO;DI SUMMA, MARCO;
2008

Abstract

Given rational numbers C_0,...,C_m and b_0,...,b_m, the mixing set with arbitrary capacities is the mixed-integer set defined by conditions s + C_t z_t  ≥ b_t , 0 ≤ t ≤ m, s ≥ 0, z_t integer, 0 ≤ t ≤ m. Such a set has applications in lot-sizing problems. We study the special case of divisible capacities, i.e. C_t /C_{t − 1} is a positive integer for 1 ≤ t ≤ m. Under this assumption, we give an extended formulation for the convex hull of the above set that uses a quadratic number of variables and constraints.
2008
Integer Programming and Combinatorial Optimization (IPCO)
9783540688860
9783540688914
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2486329
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact