language: en

[The official version of this paper has been published by]

[American Association of Artificial Intelligence (http://www.aaai.org). Paper appears in AAAI-98.]

Fast Probabilistic Modeling for Combinatorial Optimization

Shumeet Baluja
baluja@cs.cmu.edu
Justsystem Pittsburgh Research Center & Carnegie Mellon University
Scott Davies
scottd@cs.cmu.edu
School of Computer Science Carnegie Mellon University

Abstract Probabilistic models have recently been utilized for the optimization of large combinatorial search problems. However, complex probabilistic models that attempt to capture inter-parameter dependencies can have prohibitive computational costs. The algorithm presented in this paper, termed COMIT, provides a method for using probabilistic models in conjunction with fast search techniques. We show how COMIT can be used with two very different fast search algorithms: hillclimbing and Population-based incremental learning (PBIL). The resulting algorithms maintain many of the benefits of probabilistic modeling, with far less computational expense. Extensive empirical results are provided; COMIT has been successfully applied to jobshop scheduling, traveling salesman, and knapsack problems. This paper also presents a review of probabilistic modeling for combi natorial optimization.

1 Background