Publication Type

Journal Article

Version

publishedVersion

Publication Date

2013

Abstract

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.

Keywords

generic feature, search trajectory, instance-based automated parameter tuning, sequence alignment, local search algorithm

Discipline

Artificial Intelligence and Robotics | Software Engineering

Publication

Journal of the Operational Research Society

Volume

64

Issue

12

First Page

1742

Last Page

1752

ISSN

0160-5682

Identifier

10.1057/jors.2012.167

Publisher

Palgrave Macmillan

Additional URL

http://dx.doi.org/10.1057/jors.2012.167

Download

Share

COinS