Combinatorial optimization by dynamic contraction

Combinatorial optimization by dynamic contraction

0.00 Avg rating0 Votes
Article ID: iaor20003804
Country: United States
Volume: 3
Issue: 3
Start Page Number: 207
End Page Number: 224
Publication Date: Jul 1997
Journal: Journal of Heuristics
Authors:
Keywords: heuristics, combinatorial optimization
Abstract:

A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem.

Reviews

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