DASH: Dynamic Approach for Switching Heuristics

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

European Journal of Operational Research, 2016, vol. 248, issue 3, 943-953

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: Mixed-Integer Programming; Algorithm selection; Dynamic search heuristics (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715007559
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:248:y:2016:i:3:p:943-953

DOI: 10.1016/j.ejor.2015.08.018

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().