The Mixing Set with Divisible Capacities

摘要

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_(_tz_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.