 |
    |
Global Equilibrium Search Algorithms for Combinatorial Optimization Problems
Oleg Shylo1, Dmytro Korenkevych2, and Panos M. Pardalos2, 3
1Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA 15261, USA
2Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA
3National Research University Higher School of Economics, Laboratory of Algorithms and Technologies for Network Analysis (LATNA), 136 Rodionova St., Nizhny Novgorod 603093, Russia
Abstract. Global Equilibrium Search (GES) is a meta-heuristic framework that shares similar ideas with the simulated annealing method. GES accumulates a compact set of information about the search space to generate promising initial solutions for the techniques that require a starting solution, such as the simple local search method. GES has been successful for many classic discrete optimization problems: the unconstrained quadratic programming problem, the maximum satisfiability problem, the max-cut problem, the multidimensional knapsack problem and the job-shop scheduling problem. GES provides state-of-the-art performance on all of these domains when compared to the current best known algorithms from the literature. GES algorithm can be naturally extended for parallel computing as it performs search simultaneously in distinct areas of the solution space. In this talk, we provide an overview of Global Equilibrium Search and discuss some successful applications.
Keywords: discrete optimization, meta-heuristics, global equilibrium search
LNCS 7492, p. 277 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012