Re: need help on complex constraints

[Bowie Owens]

On Tue, Jan 08, 2002 at 12:15:17PM +0000, Jean-Paul Berger wrote:
> hi,
> 
> 
> i am trying to implement a scheduling algorithm in gprolog using finite 
> domains. but when i try to constrain the used ressources (steps/jobs may not 
> overlap) it takes far too much time for prolog to calculate this (10min for 
> 20 steps and 4 ressources!)
> 
> now, i am quite new to CLP, so there may be many mistakes within my code. 
> does anyone know a site, where an explanation about FD can be found 
> (exspecially about gprolog). or is there any open-source 
> scheduling-algorithm using FDs?

The GNU Prolog website
(http://pauillac.inria.fr/~diaz/gnu-prolog/manual/manual052.html) has
a complete reference of the FD facilities available in GNU Prolog. The
SICStus website (http://www.sics.se/sicstus/docs/latest/html/sicstus.html)
has documentation on their FD implementation, including a number of
constriants related to this kind of problem. The constraint you will be
most interested in is serialized.

> PS: here is the code i used. maybe someone can tell me about my mistake...? 
> (the problem seems to be in constrain_ressources/2)

There are a number of problems with the code.

- findall can't be used to collect FD variables as it does a copy_term,
that means that the variables collected will not be the ones you expect.
Try this, note that LL is a list of new variables:

L = [A,B], A #= 10 #<=> B, findall(X, member(X,L), LL), LL=[10|_].

Compare with:

L = [A,B], A #= 10 #<=> B, findall(X, member(X,L), LL), L=[10|_].

- findall can't be used to post FD constraints as they are undone by
backtracking within the call. Try this, note that the members of L
are unchanged:

length(L, 10), findall(X, (member(X,L), X #= 2), _).


- Your use of optimisation seems a little strange. Since fd_minimize will
eliminate all other solutions except for the minimum you will be cutting
off large sections of the search space. Anyway, using fd_minimize for this
kind of problem is probably not a good idea.  You will probably be better
off writing a labelling strategy that works like order_resource. Try this,
note that X is never set to either 2, 3, or 4.

L=[1,2,3,4,1,2,3,1,2], fd_minimize(member(X,L), X).


I have attached two files lambda.pl and cumulative.pl. In addition to a
few other things they implement serialized. Consult cumulative.pl and
try a query like:

D = [1,2,1],
serialized(S,D),
plus__(S,D,F),
max_element(F, LCT),
fd_minimize(fd_labeling(F), LCT).






> 
> 
> 
> :- op(255, xfx, in).
> in(A,B) :- member(A,B).
> 
> % not used
> ressource(1,1,'class1','res1').
> ressource(2,1,'class1','res2').
> ressource(3,1,'class1','res3').
> ressource(4,1,'class1','res42').
> 
> % step(ID, Start, End, Duration, Used_Ressources, Depencies, Name)
> step(1,_,_,30,[(1,1)],[],'step1').
> step(2,_,_,45,[(2,1)],[1],'step2').
> step(3,_,_,21,[(3,1)],[1],'step3').
> step(4,_,_,31,[(4,1)],[2,3],'step4').
> step(5,_,_,25,[(1,1),(2,1)],[15],'step5').
> step(6,_,_,9,[(1,1),(2,1)],[13],'step6').
> step(7,_,_,57,[(2,1)],[12,13],'step7').
> step(8,_,_,100,[(1,1)],[2,5],'step8').
> step(9,_,_,63,[(1,1)],[12],'step9').
> step(10,_,_,15,[(4,1)],[12],'step10').
> step(11,_,_,27,[(4,1)],[13],'step11').
> step(12,_,_,1023,[(1,1),(2,1),(3,1),(4,1)],[1,13],'step12').
> step(13,_,_,547,[(1,1),(4,2)],[4],'step13').
> step(14,_,_,3,[(2,1)],[7],'step14').
> step(15,_,_,99,[(2,1)],[13],'step15').
> step(16,_,_,4,[(1,1),(4,1)],[14,15],'step16').
> step(17,_,_,12,[(3,1),(2,1)],[5,7],'step17').
> step(18,_,_,78,[(4,1),(3,1)],[7,8,9],'step18').
> step(19,_,_,77,[(3,1)],[11],'step19').
> step(20,_,_,27,[(3,1)],[],'step20').
> 
> 
> 
> % In a list of steps, set the domain of Start and End for each step,
> % End = Start + Duration
> get_fd_domain([step(_,A,B,D,_,_,_)|C],S,E) :-
>       fd_domain([A,B],S,E),
>       B #=# A+D,
>       get_fd_domain(C,S,E).
> get_fd_domain([], _, _).
> 
> 
> % In a list of steps, when there is a step with a non-empty list of
> % depencies let its Start be greater then the steps it depends on End
> constrain_depencies([step(_,A,_,_,_,[N|M],_)|C],S) :-
>       step(N,_,E,_,_,_,_) in S,
>       A #># E,
>       constrain_depencies([step(_,A,_,_,_,M,_)|C],S).
> constrain_depencies([step(_,_,_,_,_,[],_)|C],S) :-
>       constrain_depencies(C,S).
> constrain_depencies([],_).
> 
> 
> % In a list of steps, when there is a step with a non-empty list of
> % required ressources its Start and End may not overlap with
> % the Start and End of other steps using the same ressource
> constrain_ressources([step(V,A,B,_,[(N,_)|M],_,_)|C],S) :-
>       findall([X,Y], (step(W,X,Y,_,D,_,_) in S, (N,_) in D, V\=W), [I|L]),!,
>       findall([X,Y], ([X,Y] in [I|L], 
> no_intervall_intersection([A,B],[X,Y])),_),
>       write(V), write([I|L]), nl,
>       constrain_ressources([step(V,A,B,_,M,_,_)|C],S).
> constrain_ressources([step(V,_,_,_,[_|M],_,_)|C],S) :-
>       write(V), write('No Conflict'), nl,
>       constrain_ressources([step(_,_,_,_,M,_,_)|C],S).
> constrain_ressources([step(V,_,_,_,[],_,_)|C],S) :-
>       write(V), write('None'), nl,
>       constrain_ressources(C,S).
> constrain_ressources([],_).
> 
> 
> % Just label all Start and End in a list of steps
> label_them([step(_,A,B,_,_,_,_)|C]) :-
>       fd_minimize(fd_labelingff([A,B]), A),
>       label_them(C).
> label_them([]).
> 
> 
> % Two intervalls don't overlap, if the distance of the two centers
> % is greater than the sum of the radiusses.
> % (Be sure that A =< B and X =< Y)
> no_intervall_intersection([A,B],[X,Y]) :-
>       C_AB   #=#     (A + B) // 2,  % center
>       C_XY   #=#     (X + Y) // 2,
>       R_AB   #=#     (B - A) // 2,  % radius
>       R_XY   #=#     (Y - X) // 2,
>       D_ABXY #=# dist(C_AB,C_XY),   % distance
>       D_ABXY #># R_AB + R_XY + 1.
> 
> 
> % Saves writing ;)
> steps(L) :- findall(step(A,B,C,D,E,F,G), step(A,B,C,D,E,F,G), L).
> 
> 
> % A principal test for no_intervall_intersection/2
> test_intervalls([A,B],[C,D]) :-
>       fd_domain([A,B,C,D],1,20),
>       B #=# A+5, D #=# C+12,
>       no_intervall_intersection([A,B],[C,D]),
>       fd_labeling([A,B]), fd_labeling([C,D]).
> 
> % A test for the whole planing procedure
> test_plan(L) :-
>       steps(L), write('STEPS LOADED'), nl,
>       fd_set_vector_max(3000),
>       get_fd_domain(L,1,2500), write('DOMAIN GOT'), nl,
>       constrain_depencies(L,L), write('DEPENCIES CONSTRAINED'), nl,
>       constrain_ressources(L,L), write('RESSOURCES CONSTRAINED'), nl,
>       label_them(L), write('LABELING'), nl.
> 
> 
> 
> 
> _________________________________________________________________
> MSN Photos is the easiest way to share and print your photos: 
> http://photos.msn.com/support/worldwide.aspx
> 
> 
> _______________________________________________
> Users-prolog mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/users-prolog
> 
-- Bowie Owens

CSIRO Mathematical & Information Sciences
phone : +61 3 9545 8055
email : address@hidden

cumulative.pl
Description: Text document

lambda.pl
Description: Text document