Abstract
Several mixed integer programming formulations have been proposed for modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (ℓ, S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Absi N., Kedad-Sidhoum S.: MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs. RAIRO Oper. Res. 41, 171–192 (2007)
Akartunalı, K., Miller, A.J.: A computational analysis of lower bounds for big bucket production planning problems. Available at Optimization Online, http://www.optimization-online.org/DB_HTML/2007/05/1668.html (2007)
Akartunalı K., Miller A.J.: A heuristic approach for big bucket multi-level production planning problems. Eur. J. Oper. Res. 193(2), 396–411 (2009)
Barany I., Van Roy T.J., Wolsey L.A.: Strong formulations for multi-item capacitated lot-sizing. Manag. Sci. 30(10), 1255–1261 (1984)
Belvaux G., Wolsey L.A.: Bc-prod: a specialized branch-and-cut system for lot-sizing problems. Manag. Sci. 46(5), 724–738 (2000)
Billington P., McClain J., Thomas L.: Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Manag. Sci. 29(10), 1126–1141 (1983)
Denizel M., Altekin F.T., Sural H., Stadtler H.: Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times. OR Spectr. 30(4), 773–785 (2008)
Eppen G.D., Martin R.K.: Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35(6), 832–848 (1987)
Floudas, C.A., Pardalos, P.M.: Encyclopedia of Optimization, 2nd edn, ISBN 978-0-387-74758-3 (2009)
Gao, Y., Zhang, G, Jie, L., Wee, H.: Particle swarm optimization for bi-level pricing problems in supply chains. J. Glob. Optim. (2010, in press). doi:10.1007/s10898-010-9595-8
Krarup, J., Bilde, O.: Plant location, set covering and economic lotsizes: an O(mn) algorithm for structured problems. Optimierung bei Graphentheoretischen und Ganzzahligen Probleme. BirkhauserVerlag, 155–180 (1977)
Mercé C., Fontan G.: MIP-based heuristics for capacitated lotsizing problems. Int. J. Prod. Econ. 85(1), 97–111 (2003)
Migdalas A., Pardalos P.M., Värbrand P.: Multilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht (1997)
Nemhauser G.L., Wolsey L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
Sahling F., Buschkühl L., Tempelmeier H., Helber S.: Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Comput. Oper. Res. 36(9), 2546–2553 (2009)
Stadtler H.: Multilevel lot sizing with setup times and multiple constrained resources: internally rolling schedules with lot-sizing windows. Oper. Res. 51(3), 487–502 (2003)
Tempelmeier H., Derstroff M.: A Lagrangean-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Manag. Sci. 42(5), 738–757 (1996)
Tempelmeier H., Helber S.: A heuristic for dynamic multi-item multi-level capacitated lotsizing for general product structures. Eur. J. Oper. Res. 75(2), 296–311 (1994)
Wu, T., Shi, L.: A new heuristic method for capacitated multi-level lot sizing problem with backlogging. In: Proceedings of the 5th Annual IEEE International Conference on Automation Science and Engineering, pp. 483–488 (2009)
Wu, T., Shi, L.: Mathematical models for capacitated multi-level production planning problems with linked lot sizes. Int. J. Prod. Res. (2011, in press). doi:10.1080/00207543.2010.535043
Wu T., Shi L., Duffie N.: An HNP-MP approach for the capacitated multi-Item lot sizing problem with setup times. IEEE Trans. Autom. Sci. Eng. 7(3), 500–511 (2010)
Wu, T., Shi, L., Akartunalı, K., Geunes, J.: An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging. Eur. J. Oper. Res. (2011a, in press). doi:10.1016/j.ejor.2011.04.029
Wu, T., Zhang, D., He, Y.: A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing. J. Syst. Sci. Syst. Eng (2011b, in press). doi:10.1007/s11518-011-5160-3
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, T., Shi, L., Geunes, J. et al. On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times. J Glob Optim 53, 615–639 (2012). https://doi.org/10.1007/s10898-011-9728-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9728-8