Search code examples
prologconstraint-programmingclpfd

Can't get minimize from CLPFD to work


Me and a friend are writing a program which is supposed to solve a CLP problem. We want to use minimize to optimize the solution but it won't work, because it keeps saying that the number we get from sum(P,#=,S) is between two numbers (for example 5..7). We haven't been able to find a good way to extract any number from this or manipulate it in any way and are therefore looking for your help.

The problem seems to arise from our gen_var method which says that each element of a list must be between 0 and 1, so some numbers come out as "0..1" instead of being set properly.

Is there any way to use minimize even though we get a number like "5..7" or any way to manipulate that number so that we only get 5? S (the sum of the elements in a list) is what we're trying to minimize.

gen_var(0, []).
gen_var(N, [X|Xs]) :-
        N > 0,
        M is N-1,
        gen_var(M, Xs),
    domain([X],0,1).

find([],_).
find([H|T],P):- match(H,P),find(T,P).

match(pri(_,L),P):-member(X,L), nth1(X,P,1).

main(N,L,P,S) :- gen_var(N,P), minimize(findsum(L,P,S),S).
findsum(L,P,S):- find(L,P), sum(P,#=,S).

Solution

  • I've slightly modified your code, to adapt to SWI-Prolog CLP(FD), and it seems to work (kind of). But I think the minimum it's always 0!

    :- use_module(library(clpfd)).
    
    gen_var(0, []).
    gen_var(N, [X|Xs]) :-
        N > 0,
        M is N-1,
        gen_var(M, Xs),
        X in 0..1 .
    
    find([], _).
    find([H|T], P):-
        match(H, P),
        find(T, P).
    
    match(pri(_,L),P):-
        member(X, L),
        nth1(X, P, 1).
    
    findsum(L,P,S) :-
        find(L, P),
        sum(P, #=, S).
    
    main(N, L, P, S) :-
        gen_var(N, P),
        findsum(L, P, S),
        labeling([min(S)], P).
    

    Is this output sample a correct subset of the expected outcome?

    ?- main(3,A,B,C).
    A = [],
    B = [0, 0, 0],
    C = 0 ;
    A = [],
    B = [0, 0, 1],
    C = 1 ;