The multi-item capacitated lot-sizing problem with setup times and shortage costs

Nabil Absi, Safia Kedad-SidhoumEur. J. Oper. Res 2008 · DOI

TL;DR

This paper tackles the complex multi-item capacitated lot-sizing problem (MCLSSP) with setup times and shortage costs, a common challenge in real-world production planning. The authors introduce a novel set of valid inequalities and a branch-and-cut framework that significantly improves the efficiency of solving these challenging optimization problems.

What Problem Does This Paper Address?

Production planning often involves deciding how much of each product to manufacture in each time period to meet demand while minimizing costs. The Multi-item Capacitated Lot-sizing Problem (MCLSSP) adds layers of complexity:

  • Multiple Items: Decisions for one product can affect others.
  • Capacitated Production: There's a limit to how much can be produced in total each period.
  • Setup Times/Costs: Producing an item incurs a fixed cost and time overhead, regardless of the quantity.
  • Shortage Costs: If demand cannot be met, there are penalties (lost sales or backlogging costs).

Existing methods often struggle with the NP-hard nature of this problem, especially when capacities are tight and shortages are allowed. This paper aims to develop a more effective approach to find optimal or near-optimal solutions for these realistic production scenarios.

Methods

The core of this paper lies in developing and integrating new mathematical tools to solve the MCLSSP:

  • Mixed Integer Programming (MIP) Formulation: The problem is first modeled using a standard MIP formulation, defining variables for production quantities, inventory levels, shortage amounts, and binary variables for production decisions.
  • Single-Period Relaxation: A simplified version of the problem is analyzed, focusing on a single time period but allowing production to satisfy demand over a range of future periods. This relaxation is crucial for deriving strong inequalities.
  • Valid Inequalities: The authors introduce and generalize several classes of valid inequalities:
  • (l, S) inequalities: These are derived from the single-period relaxation and help to strengthen the LP relaxation of the MIP.
  • Cover and Reverse Cover Inequalities: These are adapted from existing literature and generalized to incorporate shortage costs and variable resource consumption.
  • Branch-and-Cut Framework: The newly developed inequalities are integrated into a branch-and-cut algorithm. This method iteratively adds these "cuts" (inequalities) to the problem's linear programming relaxation, progressively tightening the bounds and guiding the search for an optimal integer solution.
  • Separation Heuristics: Fast combinatorial algorithms are developed to efficiently find violated inequalities during the branch-and-cut process, which is crucial for performance.

Datasets

The authors evaluated their approach using extended instances derived from the LOTSIZELIB library, originally developed by Trigeiro et al. [36]. These instances were modified to include shortage costs and other realistic parameters. The paper also mentions the use of a facility location-based formulation for comparison.

Key Insights and Ideas

  • The Power of Relaxation: Analyzing a simplified "single-period relaxation" of the MCLSSP proved to be a fertile ground for discovering strong mathematical constraints (valid inequalities) that significantly improve the overall optimization process.
  • Bridging Theory and Practice: The paper successfully bridges theoretical polyhedral analysis with practical algorithmic implementation, showing how abstract mathematical concepts can lead to tangible improvements in solving real-world problems.
  • Inequalities as "Smart Pruning": The introduced inequalities act like "smart pruning" mechanisms in the search tree of the branch-and-cut algorithm. They eliminate large portions of the search space that cannot contain optimal solutions, drastically reducing computation time.
  • Shortage Costs are Key: Explicitly modeling and generating inequalities for shortage costs, alongside setup times and capacities, is critical for accurately representing and solving realistic production planning problems.

Key Results

The paper demonstrates the effectiveness of their proposed branch-and-cut algorithm (BC+) with the new inequalities:

  • Significant Lower Bound Improvement: At the root node of the branch-and-bound tree, BC+ achieved an average lower bound improvement of 48% to 80% across different classes of instances compared to a standard branch-and-cut (BC) method.
  • Reduced Computation Time: For many instances, BC+ was able to reach comparable or better solution quality (GAP) in significantly less CPU time and with far fewer nodes explored compared to BC. For example, in Table 5, BC+ achieved a similar GAP in 53 seconds for a specific instance where BC took 1800 seconds.
  • Better Upper Bounds: The improved lower bounds from BC+ also led to better upper bounds, indicating a more efficient search for the optimal solution.
  • Effectiveness of (l, S) Inequalities: Computational tests showed that the (l, S) inequalities were generally the most effective among the families of cuts tested individually.

Limitations and Future Work

The authors acknowledge several avenues for future research:

  • Proving Facets: While they present strong inequalities, formally proving that they define facets of the convex hull of the MCLSSP problem would further strengthen the theoretical foundation.
  • Generalizing Inequalities: Extending the developed inequalities to handle more complex constraints, such as minimal production levels, minimum run constraints, multiple resources, and group setup constraints, would increase their applicability.
  • Facility Location Formulation: The paper explored a facility location-based formulation and found it promising. Further research could involve generalizing the proposed inequalities to this formulation for potentially even better performance.
  • Heuristic Integration: Exploring the integration of their approach with heuristics, such as time decomposition, could offer alternative ways to tackle large-scale problems.

Summary updated

BibTeX
@article{absi2008multi,
  author = {Nabil Absi and Safia Kedad-Sidhoum},
  title = {{The multi-item capacitated lot-sizing problem with setup times and shortage costs}},
  journal = {Eur. J. Oper. Res.},
  year = {2008},
  doi = {10.1016/j.ejor.2006.01.053},
}
Figure