Exploiting Erraticism in Search
成果类型：
Article
署名作者：
Fischetti, Matteo; Monaci, Michele
署名单位：
University of Padua
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2013.1231
发表日期：
2014
页码：
114-122
关键词：
摘要：
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.
来源URL：