Measuring instance difficulty for combinatorial optimization problems

Measuring instance difficulty for combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor20118763
Volume: 39
Issue: 5
Start Page Number: 875
End Page Number: 889
Publication Date: May 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies – studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances – provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin‐packing, graph coloring, and timetabling. For these problems – which are important abstractions of many real‐world problems – we review hardness‐revealing features as developed over decades of research, and we discuss the suitability of more problem‐independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.

Reviews

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