F. Gortazar, A. Duarte, M. Laguna and R. Martí
January 2009
The purpose of this paper is to apply the scatter search methodology to general classes of binary problems. We focus on optimization problems for which the solutions are represented as binary vectors and that may or may not include constraints. Binary problems arise in a variety of settings, including engineering design and statistical mechanics (e.g., the spin glass problem). A distinction is made between two sets of general constraint types that are handled directly by the solver and all others constraints that are addressed via penalty functions. In both cases, however, the heuristic treats the objective function evaluation as a black box. We perform computational experiments with four well-known binary optimization problems to study the efficiency and effectiveness of the proposed method. A comparison is made against both commercial software and specialized procedures on a set of 376 instances. We chose commercial software that is in nature to the proposed procedure, namely, it treats the objective function as a black box and the search is based on evolutionary optimization techniques.
Full text
