Reviving integer programming approaches for AI planning: a branch-and-cut framework
Menkes van den Briel, Thomas W. M. Vossen, Subbarao Kambhampati · 2005
The conventional wisdom in the planning community is that planners based on integer programming (IP) techniques cannot compete with satisfiability and con-straint satisfaction based planners. In this paper we challenge this perception of IP techniques by present-ing novel formulations that outperform the most effi-cient SAT-based planner that currently exists. We will present a series of IP formulations that (1) use multi-valued state variables that are represented by networks, and that (2) control the encoding length by progres-sively generalizing the notion of parallelism. The re-sulting IP encodings are solved within a branch-and-cut framework and yield impressive results.