Solving constraint optimization problems from CLP-style specifications using Heuristic search techniques

Abstract

This paper presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower bound and upper bound specifications with conventional logic programming languages, we augment a CLP language with embedded constructs for specifying the cost function and with a few higher order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP^∗ and show that CSLDNF resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP^∗ can be converted into an implicit AND/OR graph, and present an algorithm GenSolve which can branch and bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP^∗ programs.