An Integer Local Search Method with Application to Capacitated Production Planning

AAAI 1998

TL;DR

This paper introduces WSAT(OIP), a novel domain-independent local search heuristic for integer optimization, and applies it to a challenging real-world capacitated lot-sizing problem with discrete lot-sizes. The authors demonstrate that WSAT(OIP) is more robust than a state-of-the-art mixed-integer programming solver (CPLEX) in finding feasible solutions within limited time, especially under tight capacity constraints.

What Problem Does This Paper Address?

Manufacturing systems face complex production planning challenges, particularly in industries like chemicals, food, and plastics. A key problem is the capacitated lot-sizing problem (CLSP), which involves determining optimal production quantities and timings to meet customer demand while respecting resource capacities and minimizing costs. This paper focuses on a specific, real-world CLSP variant that includes the crucial constraint of discrete lot-sizes. This means products can only be produced in predefined quantities, not any arbitrary amount. This discrete nature makes many standard optimization techniques, designed for continuous or simpler integer variables, less effective or directly inapplicable. The authors aim to bridge this gap by developing a more adaptable optimization method.

Methods

The core contribution is the development and application of WSAT(OIP), a new domain-independent heuristic for integer optimization. WSAT(OIP) is an extension of the Walksat algorithm, a popular heuristic for satisfiability problems, adapted for integer variables. It operates on over-constrained integer programs (OIPs), a framework where optimization objectives are expressed through competing soft constraints rather than a single objective function. This allows for a more flexible representation of complex problems.

WSAT(OIP) employs a stochastic local search strategy. It starts with a random assignment of variable values and iteratively tries to improve a "score" that reflects the degree of constraint violation and the optimization objective. The search involves a two-stage move selection process: first, an unsatisfied constraint is chosen, and then a variable within that constraint is selected for modification. The selection of the new value for the variable aims to greedily improve the overall score. The method also incorporates elements of tabu search (to avoid recently visited states) and occasional restarts to escape local optima.

For comparison, the authors also formulate the problem using a Mixed Integer Programming (MIP) model and solve it with CPLEX 4.0, a commercial solver. They also explore a Lagrangean relaxation technique to derive lower bounds for the problem.

Datasets

The experimental evaluation uses real-world data provided by a client from the process industry. This dataset consists of 190 items and covers a planning horizon of 52 weeks. The authors do not introduce new benchmark datasets but rather apply their methods to a challenging, realistic instance of the CLSP.

Key Insights and Ideas

  • Discrete Lot-Sizes are a Major Hurdle: The paper highlights that the discrete lot-size constraint significantly complicates standard optimization approaches, making them less effective or even incapable of finding solutions.
  • OIPs as a Flexible Framework: The use of Over-Constrained Integer Programs (OIPs) proves to be a powerful way to represent complex optimization problems with competing objectives, enabling domain-independent heuristics like WSAT(OIP) to be applied.
  • Local Search Robustness: WSAT(OIP) demonstrates superior robustness compared to CPLEX, particularly when capacity constraints are tightened. This suggests that local search methods can be more resilient in finding any feasible solution under difficult conditions, even if not necessarily the absolute optimum.
  • Trade-offs in Production Planning: The study reveals a critical trade-off between labor costs and inventory costs. Reducing labor, while desirable for cost savings, can necessitate earlier production and thus higher inventory costs. The paper explores how varying labor profiles impacts the overall solution.
  • Simplicity of Local Search Models: The WSAT(OIP) model is presented as simpler than the MIP model, which can be an advantage in terms of development and understanding.

Key Results

  • Feasible Solutions: WSAT(OIP) was significantly more successful than CPLEX in finding feasible solutions within limited time, especially when capacity constraints were tightened. For instance, WSAT(OIP) could solve problems with 25 one-shift periods, while CPLEX struggled beyond 22.
  • Solution Quality: For the problems where both methods found solutions, the overall quality (production cost) was comparable, with WSAT(OIP) being slightly better in some cases.
  • Labor Profile Optimization: By analyzing various labor profiles (combinations of one and two shifts per week), the study identified potential savings of over 15% (USD 1.9 million) by reducing labor to one shift for up to 25 weeks.
  • Lower Bounds: Lagrangean relaxation provided lower bounds that indicated the fixed-capacity problems solved by the methods were near-optimal (within 1.4% of the optimal total cost).

Limitations and Future Work

  • Restricted Model for CPLEX: CPLEX was often applied to a "restricted" version of the problem (where lot-sizes were forced to equal EPQs) because it struggled with the full, unrestricted problem. This means direct comparisons on the most challenging instances are limited.
  • Runtime Limitations: Experiments were conducted with relatively short time limits (10-15 minutes) to examine many labor profiles. Longer runtimes might yield different results for CPLEX.
  • Local Optima: While WSAT(OIP) has mechanisms to escape local optima, it is a heuristic and does not guarantee finding the global optimum.
  • Future Work: The authors suggest further investigation into the effectiveness of WSAT(OIP) on other types of integer optimization problems. They also imply that exploring more sophisticated tabu search mechanisms and adaptive memory strategies within WSAT(OIP) could further enhance its performance. The potential for further cost savings by varying labor profiles also suggests this as an area for continued exploration.

Summary updated

BibTeX
@inproceedings{1998integer,
  title = {{An Integer Local Search Method with Application to Capacitated Production Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure