Venkatasubramanyan.An Integer Local Search Method with Application to Capacitated Production Planning

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 meth-ods from the literature are not directly applicable. We there-fore approach the problem with WSAT (OIP), a new domain-independent heuristic for integer optimization which gener-alizes the Walksat algorithm. WSAT (OIP) performs stochas-tic tabu search and operates on over-constrained integer pro-grams. 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