Van Vyve, Mathieu
[UCL]
Recently, several authors [ 8, 10] have argued for the use of extended formulations to tighten production planning models. In this work we present two linear-programming extended formulations of the constant-capacity lot-sizing problem with backlogging. The first one applies to the problem with a general cost function and has O(n(3)) variables and constraints. This improves on the more straightforward O(n(4)) Florian and Klein [ 2] type formulation. The second one applies when the costs satisfy the Wagner-Whitin property but it has O(n(2)) variables and O(n(3)) constraints. As a by-product, we positively answer an open question of Miller and Wolsey [ 4] about the tightness of an extended formulation for the continuous mixing set.
- Eppen, G.D., Martin, R.K.: Solving multi-item lot-sizing problems using variable definition. Operations Research 35, 832–848 (1985)
- Florian, M., Klein, M.: Deterministic production planning with concave costs and capacity constraints. Management Science 18, 12–20 (1971)
- Günlük, O., Pochet, Y.: Mixing mixed-integer inequalities. Mathematical Programming A 90, 429–457 (2001)
- Miller, A.J., Wolsey, L.: Tight MIP formulations for multi-item discrete lot-sizing problems. To appear in Operations Research.
- Pochet, Y., Wolsey, L. A.: Lot-size models with backlogging: Strong formulations and cutting planes. Mathematical Programming A 40, 317–335 (1988)
- Pochet, Y., Wolsey, L.A.: Lot-sizing with constant batches: Formulations and valid inequalities. Mathematics of Operations Research 18, 767–785 (1993)
- Pochet, Y., Wolsey, L.A.: Polyhedra for lot-sizing with Wagner-Whitin costs. Mathematical Programming A 67, 297–323 (1994)
- Van Vyve, M.: A Solution Approach of Production Planning Problems based on Compact Formulations for Single-Item Lot-Sizing Problems. PhD thesis, Faculté des Sciences, Université catholique de Louvain, June 2003.
- Wagner, H.M., Whitin, T.M.: Dynamic version of the economic lot size model. Management Science 5, 89–96 (1958)
- Wolsey, L. A.: Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation. Management Science 48, 1587–1602 (2002)
- Wolsey, L. A.: Strong formulations for mixed integer programs: valid inequalities and extended formulations. Mathematical Programming B 97, 423–447 (2003)
Bibliographic reference |
Van Vyve, Mathieu. Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity. In: Mathematical Programming, Vol. 108, no. 1, p. 53-77 (2006) |
Permanent URL |
http://hdl.handle.net/2078.1/38483 |