Black box scatter search for general classes of binary optimization problems

Black box scatter search for general classes of binary optimization problems

0.00 Avg rating0 Votes
Article ID: iaor20123268
Volume: 37
Issue: 11
Start Page Number: 1977
End Page Number: 1986
Publication Date: Nov 2010
Journal: Computers and Operations Research
Authors: , , ,
Keywords: design, heuristics
Abstract:

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 other 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 (speed) and effectiveness (solution quality) of the proposed method. Comparisons are made against both commercial software and specialized procedures on a set of 376 instances. We chose commercial software that is similar 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.

Reviews

Required fields are marked *. Your email address will not be published.