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 tough 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 an intriguing statement related to 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 create hybrid of the solutions for both solvers. The code looked pretty involved, 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 to find the same solution. But which solution is shorter? When counting lines of code, I opted to count every line except lines that contained only comments, lines of code that display output, lines of code that specify the problem parameters (there were none of these in the Xpress solution), or lines of code that configure the solver (there were none of these in the clingo solution).  Result: the Xpress-Optimizer+Xpress-Kalis hybrid solution is about 220 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.

1 comment:

  1. and which approach scales better ?