LS-LIB: A Library of Tools for Solving Production Planning Problems

Summary Much progress has been made in recent years in solving certain classes of production planning problems using mixed integer programming. One of the major challenges is how to make this expertise available and relatively easy to use for the non-specialist and the practitioner. Here we describe a modeling approach and tool LS-LIB. LS-LIB is a library of primitives to declare procedures/subroutines/global constraints in a high-level modeling language that we believe offers an interesting partial answer to this challenge. LS-LIB provides routines for problem reformulation, cut generation, and heuristic solution of instances. The user must provide an initial formulation of his problem in the chosen modeling language MOSEL. Then using knowledge of the problem the user must first classify each product or sku according to a simple three field scheme: [production type, capacity type, variant]. Then it is a simple matter to use the global constraints of LS-LIB by adding a few lines to the initial modeling language formulation to get a tightened formulation and/or call the appropriate cut generation routines. The heuristic procedures are called in a similar fashion. The result is a tool that allows researchers and end-users to improve the solution time and quality of a variety of production planning problems within minutes. The library incorporates much of the modeling knowledge concerning lot-sizing problems derived over the last twenty years, and is also easy to maintain and extend. We illustrate the use of LS-LIB on an intractable two-level problem, and a difficult multi-level problem.