Chapter 20 The Template Design Problem: A Perspective with Metaheuristics

摘要

This chapter deals with the template design problem, a hard constrained combinatorial problem with multiple applications. This problem is formulated here as a two-level combinatorial optimization problem whose solution is integer matrices. In the higher level, a metaheuristic tackles the design of a collection of templates containing multiple instances of a set of components to be produced; in the lower level an integer linear programming solver is used to determine the optimal number of times each template has to be pressed in order to fulfill production requirements as closely as possible. Three metaheuristics, i. e., hill climbing, tabu search, and genetic algorithms, have been considered in the higher level, and LPSolve, a simplex-based software for linear and integer programming problems, in the lower level. An empirical evaluation on three scenarios of increasing complexity has been performed, indicating the better performance of genetic algorithms. These results are comparable to those shown by sequential integer linear programming (ILP) models, and hint the possibility of hybrid approaches.