Publication details

Saarland University Computer Science

An Integer Local Search Method with Application to Capacitated Production Planning

Joachim Paul Walser, Ramesh Iyer, Narayan Venkatasubramanyan

Proceedings of the 15th National Conference on Artificial Intelligence, AAAI-98, pp. 373--379, AAAI press/MIT press, 1998

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.

Download PDF        Show BibTeX               

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009