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).

Wednesday, March 2, 2011

How I Beat the World Champion at Sprouts

With the help of my program Aunt Beast, I won the World Game of Sprouts Association 2010-2011 Tournament in January, 2011. The human world champion requested a follow-up match, billed by WGOSA as the “2011 Clash of the Titans” . As of March, 2011, the match is still ongoing, but in mid-February, I won the first game. Here’s how I did it.

Update I: I also won game 2. Here's my analysis.
Update II: I lost game 3, but won game 4. Analysis forthcoming.
Update III: I won game 5 and lost game 6, so I won the match. WGOSA has a write-up.