Measuring instance difficulty for combinatorial optimization problems

doi:10.1016/j.cor.2011.07.006

Return

Measuring instance difficulty for combinatorial optimization problems

2012-05-01

147

PRE

Kate Smith‐Miles *

Leo Lopes

DOI：10.1016/j.cor.2011.07.006

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2011 Elsevier Ltd. All rights reserved.

Keywords:

Algorithm selection

Combinatorial optimization

Hardness prediction

Instance difficulty

Landscape analysis

Phase transition

Traveling salesman problem

Assignment problem

Knapsack problem

Bin-packing

Graph coloring

Timetabling

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.