HYBRID SEARCH STRATEGIES FOR HETEROGENEOUS SEARCH SPACES

作     者：CARLA GOMES BART SELMAN 

作者机构：Dept. of Computer Science Cornell University Ithaca NY 14853 USA 

出 版 物：《International Journal on Artificial Intelligence Tools》 

年 卷 期：2000年第9卷第1期

页      面：45-57页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Search mixed integer programming randomization 

摘      要：Recently, there has been much interest in enhancing purely combinatorial formalisms with numerical information. For example, planning formalisms can be enriched by taking resource constraints and probabilistic information into account. The Mixed Integer Programming (MIP) paradigm from operations research provides a natural tool for solving optimization problems that combine such numeric and non-numeric information. The MIP approach relies heavily on linear program relaxations and branch-and-bound search. This is in contrast with depth-first or iterative deepening strategies generally used in artificial intelligence. We provide a detailed characterization of the structure of the underlying search spaces as explored by these search strategies. Our analysis shows that much can be gained by combining different search strategies for solving hard MIP problems, thereby leveraging each strategy s strength in terms of the combinatorial and numeric information.