Journal
INFORMS JOURNAL ON COMPUTING
Volume 28, Issue 4, Pages 766-780Publisher
INFORMS
DOI: 10.1287/ijoc.2016.0712
Keywords
lot-sizing; integer programming; local cuts; convex hull closure; quadratic programming; column generation
Categories
Funding
- EPSRC entitled MultiItem Production Planning: Theory, Computation and Practice, [EP/L000911/1]
- NSF [CMMI-0323299, CMMI-0521953]
- EPSRC [EP/L000911/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/L000911/1] Funding Source: researchfish
Ask authors/readers for more resources
Despite the significant attention they have drawn, big-bucket lot-sizing problems remain notoriously difficult to solve. Previous literature contained results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multiperiod submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation. We propose a methodology that can approximate the convex hulls of all such possible relaxations by generating violated valid inequalities. To generate such inequalities, we separate two-period projections of fractional linear programming solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation and can therefore be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available