The Application Of Valid Inequalities To The Multi-stage Lot-sizing Problem

A capacitated multi-stage lot-sizing problem for general product structures with setup and lead times is considered. The problem is formulated as a mixed integer linear program and valid inequalities that are high dimension faces of the problem's convex hull are identified. A fast separation algorithm is developed to iteratively select those inequalities that cut off the solution of the linear programming relaxation. The resulting much improved lower bounds are used in a Branch-and-Bound algorithm. Computational test results are presented. © 1995.227669680Bahl, Ritzman, Gupta, Determining lot-sizes and resource requirements a review (1987) Operations Research, 35, pp. 237-249Johnson, Montgomey, (1974) Operations Research in Production Planning, Scheduling and Inventory Control, , Wiley, New YorkZangwill, A backlogging model and a multi-echelon model of a dynamic economic lot-size production system—a network approach (1969) Management Science, 15, pp. 506-527Konno, Minimum concave cost production system a further generalization of multi-echelon model (1988) Mathematical Programming, 41, pp. 185-193Steinberg, Napier, Optimal multi-level lot-sizing for requirements planning systems (1980) Mgmt Sci., 26, pp. 1258-1271Afentakis, Gavish, Karmarkar, Computationally efficient optimal solutions to the lot-sizing problem in multistage assembly systems (1984) Mgmt Sci., 30, pp. 222-239Afentakis, Gavish, Optimal lot-sizing algorithms for complex product structures (1986) Ops Res., 34, pp. 237-249Crowston, Wagner, Williams, Economic lot size determination in multi-stage assembly systems (1973) Management Science, 19, pp. 517-527Crowston, Wagner, Dynamic lot-size models for multi-stage assembly systems (1973) Management Science, 20, pp. 517-527Schwarz, Schrage, Optimal and system myopic policies for multi-echelon production/inventory assembly systems (1975) Management Science, 21, pp. 1285-1294Goyal, Gunasekaran, Multi-stage production-inventory systems (1990) Eur. J. Opl Res., 46, pp. 1-20Maes, McClain, Van Wassenhove, Multilevel capacitated lotsizing complexicity and LP-based heuristics (1991) Eur. J. Opl Res., 53, pp. 131-148Gomory, Outline of an algorithm for integer solutions to linear programs (1958) Bulletin of the American Mathematical Society, 64, pp. 275-278Barany, Van Roy, Wolsey, Strong formulations for multi-item capacitated lot-sizing (1984) Mgmt Sci., 30, pp. 1255-1261Clark, Armentano, Echelon stock formulations for multi-stage lot-sizing with lead times (1993) International Journal of Systems Science, 24, pp. 1759-1775Vollman, Berry, Whybark, (1988) Manufacturing Planning and Control Systems, , 2nd edition, Dow-Jones, Irwin, ILClark, Scarf, Optimal policities for a multi-echelon inventory problem (1960) Management Science, 6, pp. 475-490Clark, Armentano, The application of valid inequalities to the multi-stage lot-sizing problem (1993) Technical Report #11, , 3rd edition, Faculty of Electrical Engineering, Universidade Estadual de Campinas, BrazilNemhauser, Wolsey, (1988) Integer and Combinatorial Optimization, , Wiley, New YorkVan Roy, Wolsey, Solving mixed integer programming problems using automatic reformulation (1987) Ops Res., 35, pp. 45-57Van Roy, Wolsey, Valid inequalities for mixed 0–1 programs (1986) Discr. Appl. Math., 14, pp. 199-213IBM, (1991) Optimization Subroutine Library (OSL) User's Guide, , Release 2Freund, Walpole, (1980) Mathematical Statistics, , 3rd edition, Prentice-Hall, Englewood Cliffs, NJWhite, Yeats, Skipworth, (1979) Tables for Statisticians, , 3rd edition, Thorns, Cheltenha