Template Design Under Demand Uncertainty by Integer Linear Local Search

Production planning under uncertain demands leads to optimisation problems that are hard both to model and to solve. We describe an integer linear model for a template design problem under un-certainty, 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 combi-natorial optimisation 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 in-stances much more quickly. A general-purpose local search algorithm provides a rapid and convenient way of finding high-quality solutions to complex production problems.