Exploiting Erraticism in Search

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