Measuring instance difficulty for combinatorial optimization problems

Kate Amanda Smith-Miles, Leonardo Lopes

Research output: Contribution to journalArticleResearchpeer-review

100 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)875 - 889
Number of pages15
JournalComputers and Operations Research
Volume39
Issue number5
DOIs
Publication statusPublished - 2012

Cite this

Smith-Miles, Kate Amanda ; Lopes, Leonardo. / Measuring instance difficulty for combinatorial optimization problems. In: Computers and Operations Research. 2012 ; Vol. 39, No. 5. pp. 875 - 889.
@article{2d0ffd8f860f42c28a95e7fbbe1a5257,
title = "Measuring instance difficulty for combinatorial optimization problems",
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.",
author = "Smith-Miles, {Kate Amanda} and Leonardo Lopes",
year = "2012",
doi = "10.1016/j.cor.2011.07.006",
language = "English",
volume = "39",
pages = "875 -- 889",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",
number = "5",

}

Measuring instance difficulty for combinatorial optimization problems. / Smith-Miles, Kate Amanda; Lopes, Leonardo.

In: Computers and Operations Research, Vol. 39, No. 5, 2012, p. 875 - 889.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Measuring instance difficulty for combinatorial optimization problems

AU - Smith-Miles, Kate Amanda

AU - Lopes, Leonardo

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.sciencedirect.com/science/article/pii/S0305054811001997

U2 - 10.1016/j.cor.2011.07.006

DO - 10.1016/j.cor.2011.07.006

M3 - Article

VL - 39

SP - 875

EP - 889

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 5

ER -