DASH

Dynamic approach for switching heuristics

Giovanni Di Liberto, Serdar Kadioglu, Kevin Leo, Yuri Malitsky

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Complete tree search is a highly effective method for tackling Mixed-Integer Programming (MIP) problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Yet while each new approach continued to push the state-of-the-art, parallel research began to repeatedly demonstrate that there is no single method that would perform the best on all problem instances. Tackling this issue, portfolio algorithms took the process a step further, by trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered sub-problem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among sub-problems of instances from the same MIP models. We show how to exploit these features on-the-fly in order to decide the best time to switch the branching variable selection heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of hard MIP instances show significant gains over the standard pure approach which commits to a single heuristic throughout the search.

Original languageEnglish
Pages (from-to)943-953
Number of pages11
JournalEuropean Journal of Operational Research
Volume248
Issue number3
DOIs
Publication statusPublished - 1 Feb 2016
Externally publishedYes

Keywords

  • Algorithm selection
  • Dynamic search heuristics
  • Mixed-Integer Programming

Cite this

Liberto, Giovanni Di ; Kadioglu, Serdar ; Leo, Kevin ; Malitsky, Yuri. / DASH : Dynamic approach for switching heuristics. In: European Journal of Operational Research. 2016 ; Vol. 248, No. 3. pp. 943-953.
@article{ea038481d37044b69b91c04ff25a0bc9,
title = "DASH: Dynamic approach for switching heuristics",
abstract = "Complete tree search is a highly effective method for tackling Mixed-Integer Programming (MIP) problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Yet while each new approach continued to push the state-of-the-art, parallel research began to repeatedly demonstrate that there is no single method that would perform the best on all problem instances. Tackling this issue, portfolio algorithms took the process a step further, by trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered sub-problem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among sub-problems of instances from the same MIP models. We show how to exploit these features on-the-fly in order to decide the best time to switch the branching variable selection heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of hard MIP instances show significant gains over the standard pure approach which commits to a single heuristic throughout the search.",
keywords = "Algorithm selection, Dynamic search heuristics, Mixed-Integer Programming",
author = "Liberto, {Giovanni Di} and Serdar Kadioglu and Kevin Leo and Yuri Malitsky",
year = "2016",
month = "2",
day = "1",
doi = "10.1016/j.ejor.2015.08.018",
language = "English",
volume = "248",
pages = "943--953",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

DASH : Dynamic approach for switching heuristics. / Liberto, Giovanni Di; Kadioglu, Serdar; Leo, Kevin; Malitsky, Yuri.

In: European Journal of Operational Research, Vol. 248, No. 3, 01.02.2016, p. 943-953.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - DASH

T2 - Dynamic approach for switching heuristics

AU - Liberto, Giovanni Di

AU - Kadioglu, Serdar

AU - Leo, Kevin

AU - Malitsky, Yuri

PY - 2016/2/1

Y1 - 2016/2/1

N2 - Complete tree search is a highly effective method for tackling Mixed-Integer Programming (MIP) problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Yet while each new approach continued to push the state-of-the-art, parallel research began to repeatedly demonstrate that there is no single method that would perform the best on all problem instances. Tackling this issue, portfolio algorithms took the process a step further, by trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered sub-problem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among sub-problems of instances from the same MIP models. We show how to exploit these features on-the-fly in order to decide the best time to switch the branching variable selection heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of hard MIP instances show significant gains over the standard pure approach which commits to a single heuristic throughout the search.

AB - Complete tree search is a highly effective method for tackling Mixed-Integer Programming (MIP) problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Yet while each new approach continued to push the state-of-the-art, parallel research began to repeatedly demonstrate that there is no single method that would perform the best on all problem instances. Tackling this issue, portfolio algorithms took the process a step further, by trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered sub-problem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among sub-problems of instances from the same MIP models. We show how to exploit these features on-the-fly in order to decide the best time to switch the branching variable selection heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of hard MIP instances show significant gains over the standard pure approach which commits to a single heuristic throughout the search.

KW - Algorithm selection

KW - Dynamic search heuristics

KW - Mixed-Integer Programming

UR - http://www.scopus.com/inward/record.url?scp=84945437362&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2015.08.018

DO - 10.1016/j.ejor.2015.08.018

M3 - Article

VL - 248

SP - 943

EP - 953

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -