paper available: Fast Probabilistic Modeling for Combinatorial Optimization

[Shumeet Baluja]

Fast Probabilistic Modeling for Combinatorial Optimization
-----------------------------------------------------------

Shumeet Baluja
  Justsystem Pittsburgh Research Center &
  Carnegie Mellon University

Scott Davies
  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 combinatorial optimization.


This paper is an extension of the earlier work reported in: 
   Combining Multiple Optimization Runs with Optimal Dependency Trees
   by: S. Baluja & S. Davies, June 1997.




Available from:
http://www.cs.cmu.edu/~baluja




Questions and comments are welcome. 

Shumeet Baluja