/*-------------------------------------------------------------------------*/
/* Benchmark (Finite Domain) */
/* */
/* Name : bridge.pl */
/* Title : bridge scheduling problem */
/* Original Source: P. Van Hentenryck's book and */
/* COSYTEC (version used in "Overview of a CHIP Compiler")*/
/* Adapted by : Daniel Diaz for GNU Prolog */
/* Date : October 1994 */
/* */
/* Find a scheduling that minimizes the time to build a 5-segment bridge. */
/* */
/* Solution: */
/* */
/* Optimal (End=104) */
/* */
/* [[start,0,0],[a1,4,3],[a2,2,13],[a3,2,7],[a4,2,15],[a5,2,1],[a6,5,38], */
/* [p1,20,9],[p2,13,29],[ue,10,0],[s1,8,10],[s2,4,18],[s3,4,29],[s4,4,42],*/
/* [s5,4,6],[s6,10,46],[b1,1,18],[b2,1,22],[b3,1,33],[b4,1,46],[b5,1,10], */
/* [b6,1,56],[ab1,1,19],[ab2,1,23],[ab3,1,34],[ab4,1,47],[ab5,1,11], */
/* [ab6,1,57],[m1,16,20],[m2,8,36],[m3,8,44],[m4,8,52],[m5,8,12], */
/* [m6,20,60],[l1,2,30],[t1,12,44],[t2,12,56],[t3,12,68],[t4,12,92], */
/* [t5,12,80],[ua,10,78],[v1,15,56],[v2,10,92],[k1,0,42],[k2,0,80], */
/* [stop,0,104]] */
/*-------------------------------------------------------------------------*/
/* constraint definitions */
smallereqc(X,Y,C):-
% X #=< Y+C.
fd_tell(x_plus_c_gte_y(Y,C,X)).
greatereqc(X,Y,C):-
% X #>= Y+C.
fd_tell(x_plus_c_lte_y(Y,C,X)).
q:- statistics(runtime,_),
bridge(Ld,End), statistics(runtime,[_,Y]),
write(Ld), nl,
write(End), nl,
write('time : '), write(Y), nl.
bridge(K,Ende):-
setup(K,Ende,Disj),
fd_minimize(choice(Disj,K),Ende).
setup(K,Ende,Disj):-
jobs(L),
make_vars(L,K),
member([stop,_,Ende],K),
precedence(M),
make_precedence(M,K),
max_nf(M1),
make_max_nf(M1,K),
max_ef(M2),
make_max_ef(M2,K),
min_af(M3),
make_min_af(M3,K),
min_sf(M4),
make_min_sf(M4,K),
min_nf(M5),
make_min_nf(M5,K),
resources(R),
make_disj(R,K,[],Disj1),
reverse(Disj1,Disj).
choice(Disj,K):-
disjunct(Disj),
label(K).
make_vars([],[]).
make_vars([H|T],[[H,D,A]|R]):-
duration(H,D),
fd_domain(A,0,200),
make_vars(T,R).
make_precedence([],_).
make_precedence([[A,B]|R],L):-
member([A,Ad,Aa],L),
member([B,_Bd,Ba],L),
greatereqc(Ba,Aa,Ad), % Ba #>= Aa+Ad,
make_precedence(R,L).
make_max_nf([],_).
make_max_nf([[A,B,C]|R],L):-
member([A,Ad,Aa],L),
member([B,_Bd,Ba],L),
C1 is C + Ad,
smallereqc(Ba,Aa,C1), % Ba #=< Aa+C1,
make_max_nf(R,L).
make_max_ef([],_).
make_max_ef([[A,B,C]|R],L):-
member([A,Ad,Aa],L),
member([B,Bd,Ba],L),
C1 is Ad + C - Bd,
smallereqc(Ba,Aa,C1), % Ba #=< Aa+C1,
make_max_ef(R,L).
make_min_af([],_).
make_min_af([[A,B,C]|R],L):-
member([A,_Ad,Aa],L),
member([B,_Bd,Ba],L),
greatereqc(Ba,Aa,C), % Ba #>= Aa+C,
make_min_af(R,L).
make_min_sf([],_).
make_min_sf([[A,B,C]|R],L):-
member([A,_Ad,Aa],L),
member([B,Bd,Ba],L),
C1 is C - Bd,
smallereqc(Ba,Aa,C1), % Ba #=< Aa+C1,
make_min_sf(R,L).
make_min_nf([],_).
make_min_nf([[A,B,C]|R],L):-
member([A,Ad,_Aa],L),
member([B,_Bd,Ba],L),
C1 is C + Ad,
greatereqc(Ba,Ad,C1), % Ba #>= Ad+C1,
make_min_nf(R,L).
make_disj([],_R,D,D).
make_disj([[_H,R]|T],K,Din,Dout):-
el_list(R,K,R1),
make_disj1(R1,Din,D1),
make_disj(T,K,D1,Dout).
make_disj1([],D,D).
make_disj1([H|T],Din,Dout):-
make_disj2(H,T,Din,D1),
make_disj1(T,D1,Dout).
make_disj2(_H,[],D,D).
make_disj2([A,B],[[C,D]|S],Din,Dout):-
make_disj2([A,B],S,[[A,B,C,D]|Din],Dout).
el_list([],_,[]).
el_list([H|T],L,[[A,D]|S]):-
member([H,D,A],L),
el_list(T,L,S).
disjunct([]).
disjunct([[A,B,C,D]|R]):-
disj(A,B,C,D),
disjunct(R).
disj(Aa,Ad,Ba,_Bd):-
greatereqc(Ba,Aa,Ad). % Ba #>= Aa+Ad.
disj(Aa,_Ad,Ba,Bd):-
greatereqc(Aa,Ba,Bd). % Aa #>= Ba+Bd.
label([]).
label([[_A,_Ad,Aa]|R]):-
fd_labeling(Aa),
label(R).
/*
DATA
*/
jobs([start,a1,a2,a3,a4,a5,a6,p1,p2,ue,s1,s2,s3,s4,s5,s6,
b1,b2,b3,b4,b5,b6,ab1,ab2,ab3,ab4,ab5,ab6,m1,m2,m3,m4,m5,m6,
l1,t1,t2,t3,t4,t5,ua,v1,v2,k1,k2,stop]).
duration(start,0).
duration(a1,4).
duration(a2,2).
duration(a3,2).
duration(a4,2).
duration(a5,2).
duration(a6,5).
duration(p1,20).
duration(p2,13).
duration(ue,10).
duration(s1,8).
duration(s2,4).
duration(s3,4).
duration(s4,4).
duration(s5,4).
duration(s6,10).
duration(b1,1).
duration(b2,1).
duration(b3,1).
duration(b4,1).
duration(b5,1).
duration(b6,1).
duration(ab1,1).
duration(ab2,1).
duration(ab3,1).
duration(ab4,1).
duration(ab5,1).
duration(ab6,1).
duration(m1,16).
duration(m2,8).
duration(m3,8).
duration(m4,8).
duration(m5,8).
duration(m6,20).
duration(l1,2).
duration(t1,12).
duration(t2,12).
duration(t3,12).
duration(t4,12).
duration(t5,12).
duration(ua,10).
duration(v1,15).
duration(v2,10).
duration(k1,0).
duration(k2,0).
duration(stop,0).
precedence([[start,a1],[start,a2],[start,a3],[start,a4],[start,a5],
[start,a6],[start,ue],[a1,s1],[a2,s2],[a5,s5],
[a6,s6],[a3,p1],[a4,p2],[p1,s3],[p2,s4],
[p1,k1],[p2,k1],[s1,b1],[s2,b2],
[s3,b3],[s4,b4],[s5,b5],[s6,b6],[b1,ab1],
[b2,ab2],[b3,ab3],[b4,ab4],[b5,ab5],[b6,ab6],
[ab1,m1],[ab2,m2],[ab3,m3],[ab4,m4],[ab5,m5],
[ab6,m6],[m1,t1],[m2,t1],[m2,t2],[m3,t2],
[m3,t3],[m4,t3],[m4,t4],[m5,t4],[m5,t5],
[m6,t5],[m1,k2],[m2,k2],[m3,k2],[m4,k2],
[m5,k2],[m6,k2],[l1,t1],[l1,t2],[l1,t3],
[l1,t4],[l1,t5],[t1,v1],[t5,v2],[t2,stop],
[t3,stop],[t4,stop],[v1,stop],[v2,stop],[ua,stop],
[k2,stop]]).
max_nf([[start,l1,30],[a1,s1,3],[a2,s2,3],[a5,s5,3],
[a6,s6,3],[p1,s3,3],[p2,s4,3]]).
min_sf([[ua,m1,2],[ua,m2,2],[ua,m3,2],[ua,m4,2],
[ua,m5,2],[ua,m6,2]]).
max_ef([[s1,b1,4],[s2,b2,4],[s3,b3,4],[s4,b4,4],[s5,b5,4],[s6,b6,4]]).
min_nf([[start,l1,30]]).
min_af([[ue,s1,6],[ue,s2,6],[ue,s3,6],[ue,s4,6],[ue,s5,6],[ue,s6,6]]).
resources([[crane,[l1,t1,t2,t3,t4,t5]],
[bricklaying,[m1,m2,m3,m4,m5,m6]],
[schal,[s1,s2,s3,s4,s5,s6]],
[excavator,[a1,a2,a3,a4,a5,a6]],
[ram,[p1,p2]],
[pump,[b1,b2,b3,b4,b5,b6]],
[caterpillar,[v1,v2]]]).
:- initialization(q).
