Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation

References

• Aggarwal A., Park J. Improved algorithms for economic lot-size problems. Oper. Res. (1993) 41:549–571Link, Google Scholar
• Agra A., Constantino M. Lotsizing with backlogging and start-ups: The case of Wagner-Whitin costs. Oper. Res. Lett. (1999) 25:81–88Crossref, Google Scholar
• Agra A., Constantino M. Polyhedral description of basic knapsack problems with a continuous variable. (2001) (Department of Mathematics, Univesity of Lisbon, Lisbon, Portugal) Google Scholar
• Barany I., Edmonds J., Wolsey L. A. Packing and covering a tree by subtrees. Combinatorica (1986) 6:245–257Crossref, Google Scholar
• Barany I., Van Roy T. J., Wolsey L. A. Uncapacitated lot sizing: The convex hull of solutions. Math. Programming Stud. (1984) 22:32–43Crossref, Google Scholar
• Belvaux G., Wolsey L. A. BC-PROD: A specialized branch-and-cut system for lot-sizing problems. Management Sci. (2000) 46:724–738Link, Google Scholar
• Belvaux G., Wolsey L. A. Modelling practical lot-sizing problems as mixed integer programs. Management Sci. (2001) 47:993–1007Link, Google Scholar
• Bitran G. R., Yanasse H. H. Computational complexity of the capacitated lot size problem. Management Sci. (1982) 28:1174–1186Link, Google Scholar
• The CHES Problems (1989) (Chesapeake Decision Sciences Inc., New Providence, NJ) Google Scholar
• Clark A. J., Scarf H. Optimal policies for multi-echelon inventory problems. Management Sci. (1960) 6:475–490Link, Google Scholar
• Constantino M. A polyhedral approach to production planning models: Start-up costs and times, upper and lower bounds on production. (1995) (Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, Belgium) . Ph.D. thesisGoogle Scholar
• Constantino M. A cutting plane approach to capacitated lot-sizing with start-up costs. Math. Programming (1996) 75:353–376Crossref, Google Scholar
• Constantino M. Lower bounds in lot-sizing models: A polyhedral study. Math. Oper. Res. (1998) 23:101–118Link, Google Scholar
• Cordier C., Marchand H., Laundy R., Wolsey L. A. bc-opt: A branch-and-cut code for mixed integer programs. Math. Programming (1999) 86:335–354Crossref, Google Scholar
• ILOG Cplex 7.0 User's Manual (2000) (Gentilly, France)Google Scholar
• Eppen G. D., Martin R. K. Solving multi-item lot-sizing problems using variable redefinition. Oper. Res. (1987) 35:832–848Link, Google Scholar
• Federgruen A., Tsur M. A simple forward algorithm to solve general dynamic lot-size models with n periods in O(n log n) or O(n) time. Management Sci. (1991) 37:909–925Link, Google Scholar
• Fleischmann B. The discrete lot-sizing and scheduling problem. Eur. J. Oper. Res. (1990) 44:337–348Crossref, Google Scholar
• Fleischmann B. The discrete lotsizing and scheduling problem with sequence-dependent setup costs. (1994) 75:395–404Google Scholar
• Florian M., Klein M. Deterministic production planning with concave costs and capacity constraints. Management Sci. (1971) 18:12–20Link, Google Scholar
• Günlük O., Pochet Y. Mixing mixed integer inequalities. Math. Programming (2001) 90:429–457Crossref, Google Scholar
• Karmarkar U. S., Schrage L. S. The deterministic dynamic product cycling problem. Oper. Res. (1985) 33:326–345Link, Google Scholar
• Krarup J., Bilde O., Collatz L. Plant location, set covering and economic lot sizes: An O(mn) algorithm for structured problems. Optimierung bei Graphentheoretischen und Ganzzahligen Probleme (1977) (Birkhauser Verlag, Basel, Switzerland) 155–180Crossref, Google Scholar
• Kuik R., Salomon M., van Wassenhove L. N. Batching decisions: Structure and models. Eur. J. Oper. Res. (1994) 75:243–263Crossref, Google Scholar
• Leung J. M. Y., Magnanti T. L., Vachani R. Facets and algorithms for capacitated lot-sizing. Math. Programming (1989) 45:331–359Crossref, Google Scholar
• Loparic M. Stronger mixed 01 models for lot-sizing problems. (2001) (Faculty of Engineering, Université Catholique de Louvain, Louvain-la-Neuve, Belgium) . Ph.D. thesisGoogle Scholar
• Loparic M., Marchand H., Wolsey L. A. Dynamic knapsack sets and capacitated lot-sizing. Math. Programming B. (2002) . ForthcomingGoogle Scholar
• Loparic M., Pochet Y., Wolsey L. A. The uncapacitated lot-sizing problem with sales and safety stocks. Math. Programming (2001) 89:487–504Crossref, Google Scholar
• Love S. F. Bounded production and inventory models with piecewise concave costs. Management Sci. (1973) 20:313–318Link, Google Scholar
• Marchand H. A polyhedral study of the mixed knapsack set and its use to solve mixed integer programs. (1998) (Faculty of Engineering, Université Catholique de Louvain, Louvain-la-Neuve, Belgium) . Ph.D. thesisGoogle Scholar
• Miller A., Wolsey L. A. Tight MIP formulations for multiitem discrete lot-sizing problems. (2001a) (Universite Catholique de Louvain, Louvain-la-Neuve, Belgium) Google Scholar
• Miller A., Wolsey L. A. Tight formulations for some simple MIPs and convex objective IPs. (2001b) (CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium) Google Scholar
• Miller A., Nemhauser G. L., Savelsbergh M. W. P. On the polyhedral structure of a multi-item capacitated lot-sizing problems with set-up times by branch-and-cut. (2000a) (CORE DP 2000/52, Université Catholique de Louvain, Louvain-la-Neuve, Belgium) Google Scholar
• Miller A., Nemhauser G. L., Savelsbergh M. W. P. Solving a multi-item production planning model with set-up times. (2000b) (CORE DP 2000/39. Université Catholique de Louvain, Louvain-la-Neuve, Belgium) Google Scholar
• Padberg M. W., Van Roy T. J., Wolsey L. A. Valid inequalities for fixed charge problems. Oper. Res. (1985) 33:842–861Link, Google Scholar
• Pochet Y. Valid inequalities and separation for capacitated economic lot-sizing. Oper. Res. Lett. (1988) 7:109–116Crossref, Google Scholar
• Pochet Y., Jünger M., Naddef D. Mathematical programming models and formulations for deterministic production planning problems. Computational Combinatorial Optimization (2001) (Lecture Notes in Computer Science LNCS 2241, Springer, Berlin-Heidelberg, Germany) 57–111Crossref, Google Scholar
• Pochet Y., Wolsey L. A. Lot-size models with backlogging: Strong formulations and cutting planes. Math. Programming (1988) 40:317–335Crossref, Google Scholar
• Pochet Y., Wolsey L. A. Lot-sizing with constant batches: Formulation and valid inequalities. Math. Oper. Res. (1993) 18:767–785Link, Google Scholar
• Pochet Y., Wolsey L. A. Polyhedra for lot-sizing with Wagner-Whitin costs. Math. Programming (1994) 67:297–324Crossref, Google Scholar
• Pochet Y., Wolsey L. A., Cook W., Lovasz L., Seymour P. Algorithms and reformulations for lot-sizing problems. Combinatorial Optimization (1995) 20(American Mathematical Society, Providence, RI) . DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Rardin R., Wolsey L. A. Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. Eur. J. Oper. Res. (1993) 71:95–109Crossref, Google Scholar
• Simpson N.C., Erenguc S. S. Production planning in multiple stage manufacturing environments with joint costs, limited resources and set-up times. (1998) (Technical Report, Department of Management Science and Systems, University of Buffalo, Buffalo, NY) Google Scholar
• Vanderbeck F. Lot-sizing with start-up times. Management Sci. (1998) 44:1409–1425Link, Google Scholar
• van Eijl C. A. A polyhedral approach to the discrete lot-sizing and scheduling problem. (1996) (Technical University of Eindhoven, Eindhoven, The Netherlands) . Ph.D. thesisGoogle Scholar
• van Eijl C. A., van Hoesel C. P. M. On the discrete lot-sizing and scheduling problem with Wagner-Whitin costs. Oper. Res. Lett. (1997) 20:7–13Crossref, Google Scholar
• van Hoesel C. P. M. Models and algorithms for single-item lot-sizing problems. (1991) (Erasmus University, Rotterdam, The Netherlands) . Ph.D. thesisCrossref, Google Scholar
• van Hoesel C. P. M., Kolen A. W. J. A class of strong valid inequalities for the discrete lot-sizing and scheduling problem. (1993) (Eindhoven University of Technology, Eindhoven, The Netherlands) Google Scholar
• van Hoesel C. P. M., Kuik R., Salomon M., van Wassenhove L. N. The single item discrete lot-sizing and scheduling problem: Optimization by linear and dynamic programming. Discrete Appl. Math. (1994) 48:289–303Crossref, Google Scholar
• van Hoesel C. P. M., Kuik R. A linear description of the discrete lot-sizing and scheduling problem. Eur. J. Oper. Res. (1994) 75(2):342–353Crossref, Google Scholar
• van Hoesel C. P. M., Wagelmans A. P. M. An O(T3) algorithm for the economic lot-sizing problem with constant capacities. Management Sci. (1996) 42:142–150Link, Google Scholar
• van Hoesel C. P. M., Wagelmans A. P. M. Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems. Math. Oper. Res. (2001) 26:339–357Link, Google Scholar
• van Hoesel C. P. M., Wagelmans A. P. M., Wolsey L. A. Polyhedral characterization of the economic lot-sizing problem with start-up costs. SIAM J. Discrete Math. (1994) 7:141–151Crossref, Google Scholar
• Van Vyve M. An integral extended formulation of size O(T3) for the single item lot-sizing problem with constant capacities and backlogging. (2001) . Internal Report, CORE, Université Catholique de Louvain, Louvain-la-Neuve, BelgiumGoogle Scholar
• Van Vyve M. Algorithms for constant capacity lot-sizing problems. (2002) . Internal Report, CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium. ForthcomingGoogle Scholar
• Wagelmans A. P. M., van Hoesel C. P. M., Kolen A. W. J. Economic lot-sizing: An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case. Oper. Res. (1992) 40(Supplement 1):145–156Link, Google Scholar
• Wagner H. M., Whitin T. M. Dynamic version of the economic lot size model. Management Sci. (1958) 5:89–96Link, Google Scholar
• Wolsey L. A. Uncapacitated lot-sizing problems with start-up costs. Oper. Res. (1989) 37:741–747Link, Google Scholar
• Wolsey L. A. Integer programming for production planning and scheduling. (1999) (Presented at Chorin Winter School, Chorin, Germany) Google Scholar
• XPRESS-MP Optimiser, Release 12.5 (2001) (Dash Associates, Northants, U.K) Google Scholar
• Zangwill W. I. A backlogging model and a multi-echelon model of a dynamic economic lot size production system—A network approach. Management Sci. (1969) 15:506–526Link, Google Scholar