Tuesday, September 20, 2011

Open-source answer set solver vs Fico Xpress Optimization Suite

Fico's Xpress Optimization Suite is used by American Airlines, Avis, Honeywell, and the NFL to solve industrial-sized problems in operations research. I was reading one of Fico's white papers, Hybrid MIP/CP solving with Xpress-Optimizer and Xpress-Kalis (May, 2009), when I came across the following statement about a problem in machine assignment and sequencing.
"It is possible to implement this problem entirely either with Xpress-Optimizer or wit Xpress-Kalis. However, already for this three machines – 12 jobs instance the problem is extremely hard for either technique on its own." [Section 3.4 ("Results"), page 19, italics mine]
Fico approached this dilemma by creating a hybrid of the solutions for both solvers. The code looked complicated, though, and the problem itself didn't seem that hard. I wanted to see if I was missing something, so I wrote it up in the language of the open-source answer-set solver Clingo.
According to the paper, "Optimality is proven within a few seconds on a Pentium IV PC." It takes clingo 3.5 seconds on an Athlon 64 (a similar CPU) to find the same solution. The Xpress-Optimizer+Xpress-Kalis hybrid solution is about 220 lines of code (LOC), while the Clingo solution is about 20 LOC. (*)

According to Section 4 (Summary), "Hybrid solution algorithms need to be developed, implemented, and tested on a case-by-case basis, meaning a considerable investment in terms of development effort and requiring a good understanding of the solution methods and solvers involved."

Indeed. Or you could just use Clingo.

(*)  When counting LOC, I ignored lines that consisted only of
  • comments,
  • code for displaying output,
  • code for specifying the problem parameters (there were none of these in the Xpress solution), or
  • code for configuring the solver (there were none of these in the clingo solution).