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.

#const maxtime = 39.
machine(1..3).
product(1..12).
% table2(P,T1,T2,T3,D1,D2,D3,S,E) :- product P costs C1,C2,and C3 and takes D1,D2,D3
% duration on machines 1,2,3, and must start on or after time S, and must end before time E.
table2(1,12,6,7,10,14,13,2,32).
table2(2,13,6,10,7,9,8,4,33).
table2(3,10,4,6,11,17,15,5,36).
table2(4,8,4,5,6,9,12,7,37).
table2(5,12,6,7,4,6,10,9,39).
table2(6,10,5,6,2,3,4,0,34).
table2(7,7,4,5,10,15,16,3,30).
table2(8,9,5,5,8,11,12,6,26).
table2(9,10,5,7,10,14,13,11,36).
table2(10,8,4,5,8,11,14,2,38).
table2(11,15,8,9,9,12,16,3,31).
table2(12,13,7,7,3,5,6,4,22).
cost(P,1,C1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
cost(P,2,C2) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
cost(P,3,C3) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,1,D1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,2,D2) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
dur(P,3,D3) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
legalworktime(P,S..E-1) :- table2(P,C1,C2,C3,D1,D2,D3,S,E).
% machine(P,M). We choose to build product P on machine M.
% start(P,T). We choose to start building product P at time T.
% Each product is built on exactly one machine.
1 { machine(P, M) : machine(M) } 1 :- product(P).
% Each product starts at exactly one time.
1 { start(P, S) : legalworktime(P,S) } 1 :- product(P).
% machinetime(P,M,T) :- machine is working on product P at time T.
machinetime(P,M,S..S+D-1) :- start(P,S), machine(P,M), dur(P,M,D).
% machinetime(P,T) :- product P is being worked on at time T.
machinetime(P,T) :- machinetime(P,M,T).
:- machinetime(P,M,T), machinetime(Q,M,T), P != Q.
:- machinetime(P,T), not legalworktime(P,T).
% run(P,M,S,E) :- machine is building P at times T, where S ≤ T < E.
% (used only for output)
run(P,M,S,S+D) :- product(P), machine(P,M), start(P,S), dur(P,M,D).
#hide.
#show run/4.
#show cost/1.
% cost(P,C). product P costs $C, given the machine we are making it on
cost(P,C) :- machine(P,M), cost(P,M,C).
totalcost(Cost) :- Cost = #sum [cost(P,C) : product(P) = C].
#minimize [totalcost(Cost) = Cost].

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.

and which approach scales better ?

ReplyDelete