Template Design Under Demand Uncertainty by Integer Linear Local Search

Abstract

Production planning under uncertain demands leads to optimization problems that are hard both to model and to solve. We describe an integer linear model for a template design problem under uncertainty, and investigate its solution by a general-purpose local search algorithm for integer linear programs. Several such algorithms have previously been proposed as tools for solving large combinatorial optimization problems, and ours is based on a recent Boolean Satisfiability algorithm. In experiments it was slower than other methods on small instances, but rapidly outstripped them as the problem size and number of templates increased. It also found near-optimal solutions to all instances much more quickly. A general-purpose local search algorithm provides a rapid and convenient way of finding high-quality solutions to complex production problems.