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 C
lingo 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.
(*) 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).
and which approach scales better ?
ReplyDelete