Download slides here (gzipped PostScript file).
This talk is on modeling and solving the capacitated economic lot-sizing problem that arises in production planning.
The problem is to find a production plan that will meet the demand dt > 0 of a product over NT time periods. There exists a capacity limit ct on the amount of production in period t. If we produce xt units in period t, a fixed set-up cost ft and a variable production cost pt xt is charged. In addition, if st units are kept in stock from period t to t+1, an inventory holding cost of ht st is incurred. We would like find a production plan that minimizes the total production and inventory costs.
A fixed charge network flow formulation of the problem is given in Slide 4. The network has a source node for total production and a sink node for each demand period.
Different versions of the problem are classified and a generic formulation is given in Slides 6 and 7. The generic model handles multiple products and backlogging of a product (negative inventory).
The motivation for developing a modeling and branch-cut system specifically for the lot-sizing problem is to make use of the knowledge created by research over the last 15 years. EMOSL (Extended Modelling and Subroutine Library) of XPRESS enables the user to create a model in mps format by using a language based on lot-sizing terminology. Routines to generate valid inequalities, seperation routines and specialized heuristics are included in the optimizer module.
The system has been tested on a testbed of various types of lot-sizing problems. An order of 10 speedup in run time is achieved in some of the test problems.