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.

Keywords:

• Template design
• Demand uncertainty
• Integer linear local search

Acknowledgements

S. Armagan Tarim is partially supported by Science Foundation Ireland under grant No. 03/CE3/I405 as part of the Centre for Telecommunications Value-Chain-Driven Research (CTVR). This material is also based, in part, upon works supported by the Science Foundation Ireland under grant No. 00/PI.1/C075.