Program decomposition and lazy_findall

Question

I like the idea of lazy_findall as it helps me with keeping predicates separated and hence program decomposition.

What are the cons of using lazy_findall and are there alternatives?

---

Below is my "coroutine" version of the branch and bound problem.

It starts with the problem setup:

domain([[a1, a2, a3], 
        [b1, b2, b3, b4],
        [c1, c2]]).

price(a1, 1900).
price(a2,  750).
price(a3,  900).
price(b1,  300).
price(b2,  500).
price(b3,  450).
price(b4,  600).
price(c1,  700).
price(c2,  850).

incompatible(a2, c1).
incompatible(b2, c2).
incompatible(b3, c2).
incompatible(a2, b4).
incompatible(a1, b3).
incompatible(a3, b3).

Derived predicates:

all_compatible(_, []).
all_compatible(X, [Y|_]) :- incompatible(X, Y), !, fail.
all_compatible(X, [_|T]) :- all_compatible(X, T).

list_price(A, Threshold, P) :- list_price(A, Threshold, 0, P).
list_price([], _, P, P).
list_price([H|T], Threshold, P0, P) :-
    price(H, P1),
    P2 is P0 + P1,
    P2 =< Threshold,
    list_price(T, Threshold, P2, P).

path([], []).
path([H|T], [I|Q]) :-
    member(I, H),
    path(T, Q),
    all_compatible(I, Q).

The actual logic:

solution([], Paths, Paths, Value, Value).
solution([C|D], Paths0, Paths, Value0, Value) :-
    (   list_price(C, Value0, V)
    ->  (   V < Value0
        ->  solution(D, [C], Paths, V, Value)
        ;   solution(D, [C|Paths0], Paths, Value0, Value)
        )
    ;   solution(D, Paths0, Paths, Value0, Value)   
    ).

The glue

solution(Paths, Value) :-
    domain(D),
    lazy_findall(P, path(D, P), Paths0),
    solution(Paths0, [], Paths, 5000, Value).

---

Here is an alternative no-lazy-findall solution by @gusbro: https://stackoverflow.com/a/68415760/1646086

Answer 1

I am not familiar with lazy_findall but I observe two "drawbacks" with the presented approach:

1. The code is not as decoupled as one might want, because there is still a mix of "declarative" and "procedural" code in the same predicate. I am putting quotes around the terms because they can mean a lot of things but here I see that path/2 is concerned with both generating paths AND ensuring that they are valid. Similarly solution/5 (or rather list_price/3-4) is concerned with both computing the cost of paths and eliminating too costly ones with respect to some operational bound.
2. The "bounding" test only happens on complete paths. This means that in practice all paths are generated and verified in order to find the shortest one. It does not matter for such a small problem but might be important for larger instances. Ideally, one might want to detect for instance that the partial path [a1,?,?] will never bring a solution less than 2900 without trying all values for b and c.

My suggestion is to instead use clpfd (or clpz, depending on your system) to solve both issues. With clpfd, one can first state the problem without concern for how to solve it, then call a predefined predicate (like labeling/2) to solve the problem in a (hopefully) clever way.

Here is an example of code that starts from the same "setup" predicates as in the question.

state(Xs,Total):-
    domain(Ds),
    init_vars(Ds,Xs,Total),
    post_comp(Ds,Xs).


init_vars([],[],0).
init_vars([D|Ds],[X|Xs],Total):-
    prices(D,P),
    length(D,N),
    X in 1..N,
    element(X, P, C),
    Total #= C + Total0,
    init_vars(Ds,Xs,Total0).

prices([],[]).
prices([V|Vs],[P|Ps]):-
    price(V,P),
    prices(Vs,Ps).

post_comp([],[]).
post_comp([D|Ds],[X|Xs]):-
    post_comp0(Ds,D,Xs,X),
    post_comp(Ds,Xs).

post_comp0([],_,[],_).
post_comp0([D2|Ds],D1,[X2|Xs],X1):-
    post_comp1(D1,1,D2,X1,X2),
    post_comp0(Ds,D1,Xs,X1).    

post_comp1([],_,_,_,_).
post_comp1([V1|Vs1],N,Vs2,X1,X2):-
    post_comp2(Vs2,1,V1,N,X2,X1),
    N1 is N+1, 
    post_comp1(Vs1,N1,Vs2,X1,X2).

post_comp2([],_,_,_,_,_).
post_comp2([V2|Vs2],N2,V1,N1,X2,X1):-
    post_comp3(V2,N2,X2,V1,N1,X1),
    N3 is N2 + 1,
    post_comp2(Vs2,N3,V1,N1,X2,X1).

post_comp3(V2,N2,X2,V1,N1,X1) :-
    (  ( incompatible(V2,V1) 
       ; incompatible(V1,V2) 
       )
    -> X2 #\= N2 #\/ X1 #\= N1
    ;  true
    ).

Note that the code is relatively straightforward, except for the (quadruple) loop to post the incompatibility constraints. This is due to the way I wanted to reuse the predicates in the question. In practice, one might want to change the way the data is presented.

The problem can then be solved with the following query (in SWI-prolog):

?- state(Xs, T), labeling([min(T)], Xs).
T = 1900, Xs = [2, 1, 2] ?

In SICStus prolog, one can write instead:

?- state(Xs, T), minimize(labeling([], Xs), T).
Xs = [2,1,2], T = 1900 ?

Another short predicate could then transform back the [2,1,2] list into [a2,b1,c2] if that format was expected.