Exploiting Erraticism in Search

Matteo Fischetti () and Michele Monaci ()
Additional contact information
Matteo Fischetti: Department of Information Engineering, University of Padova, 35131 Padova, Italy
Michele Monaci: Department of Information Engineering, University of Padova, 35131 Padova, Italy

Operations Research, 2014, vol. 62, issue 1, 114-122

Abstract: High sensitivity to initial conditions is generally viewed as a drawback of tree search methods because it leads to erratic behavior to be mitigated somehow. In this paper we investigate the opposite viewpoint and consider this behavior as an opportunity to exploit. Our working hypothesis is that erraticism is in fact just a consequence of the exponential nature of tree search that acts as a chaotic amplifier, so it is largely unavoidable. We propose a bet-and-run approach to actually turn erraticism to one's advantage. The idea is to make a number of short sample runs with randomized initial conditions, to bet on the “most promising” run selected according to certain simple criteria, and to bring it to completion. Computational results on a large testbed of mixed integer linear programs from the literature are presented, showing the potential of this approach even when embedded in a proof-of-concept implementation.

Keywords: enumerative algorithms; mixed integer programming; restart (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1231 (application/pdf)

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:inm:oropre:v:62:y:2014:i:1:p:114-122

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().