2005 · 46 citations · 16 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceOptimizationCombinatorial OptimizationConstraint SatisfactionConstraint SolvingDiscrete OptimizationHeuristic SearchInteger ProgrammingBranch-and-cutInteger Programming ModelsState Variables
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.
16