Exploiting Erraticism in Search

作     者：Fischetti, Matteo Monaci, Michele 

作者机构：Univ Padua Dept Informat Engn I-35131 Padua Italy 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2014年第62卷第1期

页      面：114-122页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Progetto di Ateneo on "Computational Integer Programming" of the University of Padova MiUR, Italy (PRIN project "Integrated Approaches to Discrete and Nonlinear Optimization") 

主　　题：enumerative algorithms mixed integer programming restart 

摘      要：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.