An Integer Local Search Method with Application to Capacitated Production Planning

Joachim P. Walser, Ramesh Iyer, Narayan Venkatasubramanyan

Production planning is an important task in manufacturing systems. We consider a real-world capacitated lot-sizing problem (CLSP) from the process industry. Because the problem requires discrete lot-sizes, domain-specific methods from the literature are not directly applicable. We therefore approach the problem with WSAT (OIP), a new domain-independent heuristic for integer optimization which generalizes the Walksat algorithm. WSAT (OIP) performs stochastic tabu search and operates on over-constrained integer programs. We empirically compare WSAT (OIP) to a state-of-the-art mixed integer programming branch-and-bound solver (CPLEX 4.0) on real problem data. We find that integer local search is considerably more robust than MIP branch-and-bound in finding feasible solutions in limited time, and branch-and-bound can only solve a sub-class of the CLSP with discrete lot-sizes. With respect to production cost, both methods find solutions of similar quality.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.