2

I'm trying to solve a CSP where I need to distribute cocktails over bartenders so that each bartender has at most one cocktail and all cocktails are given a bartender. I solved it by creating a list of clpfd variables,first giving them the full domain of all bartenders and then removing all bartenders that don't know how to make that cocktail.
My code works, but there is one problem: it's too slow. If I look in the profiler, remove_domain gets called 2000 times(for the input I'm giving my program), while it's Redo statistic is >100 000. What do I need to change in one of these functions(or both) so that prolog doesn't need to backtrack?

produce_domains(_,_,[],[]) :- !.
produce_domains(Bartenders,NBartenders,[Cocktail|Cocktails],[Var|Vars]) :-
    Var in 1..NBartenders,
    remove_domain(Bartenders,NBartenders,Cocktail,Var),!,
    produce_domains(Bartenders,NBartenders,Cocktails,Vars),!.

remove_domain([],0,_,_) :- !.
remove_domain([Bartender|Bartenders],NBartenders,Cocktail,Var) :-
    (\+ member(Cocktail,Bartender) -> Var #\= NBartenders;!),!,
    NNBartenders is NBartenders - 1,
    remove_domain(Bartenders,NNBartenders,Cocktail,Var),!.

I have already read this related question, but I am using the latest Windows build of SWI-Prolog(5.10.5), so that shouldn't be the problem here.

Community
  • 1
  • 1
J-Gamer
  • 21
  • 2
  • 2
    Cuts dont mix well with CLP(FD). Try instead to reformulate your problem **without** member, \+, etc ... (maybe all_different could help) – CapelliC Mar 23 '14 at 18:00

1 Answers1

2

You do not need so many !/0: Prolog can often tell that your predicates are deterministic.

Let me first offer the following version of your code. It uses names that are more relational, contains no !/0 and uses higher-order predicates to make the code shorter.

:- use_module(library(clpfd)).

bartenders_cocktails_variables(Bs, Cs, Vs) :-
        length(Bs, LBs),
        maplist(bartenders_cocktail_variable(Bs, LBs), Cs, Vs).

bartenders_cocktail_variable(Bs, N, C, V) :-
        V in 1..N,
        foldl(compatible_bartender(C,V), Bs, 1, _).

compatible_bartender(C, V, Cs, N0, N1) :-
        (   member(C, Cs) -> true
        ;   V #\= N0
        ),
        N1 #= N0 + 1.

Notice that I am counting upwards instead of downwards to enumerate the bartenders (which are just lists of cocktails they are able to mix), since this seems more natural. I was also able to omit a (\+)/1 by simply switching the branches of the if-then-else.

Example query, showing that the predicate is deterministic in this use case:

?- bartenders_cocktails_variables([[a,b],[a,b],[x,y]], [x,a,b], Vars).
Vars = [3, _G1098, _G1101],
_G1098 in 1..2,
_G1101 in 1..2.

We see: Cocktail x must be mixed by the third bartender etc.

I think this part of your program may not be responsible for the slow performance you are describing. Maybe other parts of your program are (unintentionally) not deterministic? Maybe try different labeling strategies or other constraints? We may be able to help you more if you post more context.

mat
  • 40,498
  • 3
  • 51
  • 78
  • There is a slight problem: foldl doesn't exist in swi-prolog 5.10.5... So now I notice my comment on that I'm using the latest Windows build isn't correct, but I put an implementation of foldl in there myself. Now the bartenders_cocktails_variables is getting called exactly the right amount of times(once for each order), but it takes 60% of the calculation time. The other 40% is in clfpd:all_distinct. 39 of those 60% are calls to clfpd:#\=/2. As for the scale: compatible_bartender has 2.7 million calls and 4.1 million redo's in the profiler. – J-Gamer Mar 24 '14 at 10:37
  • If it's not already the case, consider posting `all_distinct/1` only *after* the compatibility constraints are stated (that is, *after* `bartenders_cocktails_variables/3`), since then more things are already known and `all_distinct/1` needs to do less work. Also, instead of the `#\=/2` constraints, you can consider building up a domain (like `1\/3\/7..9`) and posting only one `in/2` constraint for each variable, instead of posting one `in/2` constraint and then several disequalities. You can easily adapt `compatible_bartender/5` to construct a fitting domain for each cocktail. – mat Mar 24 '14 at 13:26
  • There is indeed only one all_distinct in the whole program, so that's correct. I had tried building up the domain, but this for example wouldn't work: – J-Gamer Mar 24 '14 at 19:06
  • Ok, I was too fast with my previous comment: I did get building the domain up instead of breaking it down done, and now the program is slightly faster. Still not fast enough for the assignment though. – J-Gamer Mar 24 '14 at 19:25