Rafael Martí & Manuel Laguna

Black-Box Solvers In Combinatorial Optimization 

Abstract

Black box optimizers have a long tradition in the field of operations research. These procedures treat the objective function evaluation as a black box and therefore do not take advantage of its specific structure. Black-box optimization refers to the process in which there is a complete separation between the evaluation of the objective function —and perhaps other functions used to enforce constraints— and the solution procedure. The challenge of optimizing black boxes is to develop methods that can produce outcomes of reasonable quality without taking advantage of problem structure and employing a computational effort that is adequate for the context.

Holland’s (1975) genetic algorithms proposal was in fact a black-box optimizer that used an array of bits as the generic representation. The proposed procedure did not include local search and the standard genetic operators (such as single-point crossover) were not linked to the problem context. As GAs became more popular and researchers and practitioner applied them to many hard optimization problems, the context-independent nature of the original proposal began to vanish when improved outcomes were obtained by the addition of problem structure. During the last years we worked on the adaptation of metaheuristic methodologies to deal with black-box combinatorial optimization. We classified the problems according to their solution representation: permutation, binary, and integer to create solvers in each family. In this talk we will review commercial black-box solvers, such as Opttek’s OptQuest, Palisade’s Evolver and Frontline’s Premium Solver, and compare their performance with our metaheuristic implementations based on the Scatter Search methodology on many different optimization problems.

Short CV – Rafael Martí

Rafael Martí is Professor of Statistics and Operations Research at the University of Valencia, Spain. He received a doctoral degree in Mathematics from the University of Valencia in 1994. He has done extensive research in metaheuristics for hard optimization problems.

Dr Martí has about 200 publications, half of them in indexed journals (JCR), including EJOR, Informs JoC, IIE Transactions, JOGO, C&OR, and Discrete and Applied Maths. He is the co-author of Scatter Search (Kluwer 2003) and The Linear Ordering Problem (Springer 2011) monographs, and has secured an American patent. Prof. Martí is currently Area Editor in the Journal of Heuristics, Associate Editor in the Math. Prog. Computation, and the Int. Journal of Metaheuristics. He is Senior Research Associate of OptTek Systems (USA), and has given about 50 invited and plenary talks. Dr. Martí has been invited Professor at the University of Colorado (USA), University of Molde (Norway), University of Graz (Austria), and University of Bretagne-Sud (France).

Short CV – Manuel Laguna

Manuel Laguna is the MediaOne Professor of Management Science and Director of Global Initiatives at the Leeds School of Business of the University of Colorado Boulder. He started his academic career at the University of Colorado in 1990, after receiving master’s (1987) and doctoral (1990) degrees in Operations Research and Industrial Engineering from the University of Texas at Austin.

He has done extensive research in the interface between computer science, artificial intelligence and operations research, resulting in over one hundred publications, including four books. He has received research funding from private industry and government agencies such as the National Science Foundation, the Office of Naval Research and the Environmental Protection Agency. He is co-founder of OptTek Systems, a Boulder-based software and consulting company that provides optimization solutions. He is the editor-in-chief of the Journal of Heuristics and has been Division Chair, Senior Associate Dean and Interim Dean at the Leeds School of Business.