Compilation to Integer Linear Programming

• Motivations

  • Ability to handle numeric quantities, and do optimization
  • Heuristic value of the LP relaxation of ILP problems
  • Deep connections between CSP and ILP (Chandru & Hooker, 99)

• Conversion

  • Explicitly set up ILP inequalities corresponding to the disjunctive plan (Bylander, 97)
  • Convert a SAT/CSP encoding to ILP inequalities
    • E.g. X v ~Y v Z => x + (1 - y) + z >= 1

• Solving

  • Use LP relaxation as a heuristic (akin to Greedy Regression Graphs), or as a seed (for local search)
  • Solve using standard methods (not competitive with SAT approaches)

Previous slide

Next slide

Back to first slide

View graphic version