Change list domain swi-prolog clpfd

Question

I'm using SWI-Prolog with clpfd library. The problem is that I generate a list of length N with items in 1..2^(N-1), constraining this list to have some properties and calculating the maximum of the ones that verify the constraint. After that I have to find the minimum of these maxima but there are too many cases to evaluate and Prolog ends to freeze.

maxConstrain(N,Max) :-
   listN(List,N),
   label(List),
   constrain(List),
   max_list(List,Max).

minMaxConstrain(N,M) :-
   findall(Max,maxConstrain(N,Max),Maxs), min_list(Maxs,M).

listN(-List,+N) generate a list with N items in 1..2^(N-1).

maxConstrain(+N,-Max) gives the maximum of List if it verify the constraint.

minMaxConstrain(+N,-M) gives the minimum of all the evaluations of maxConstrain(N,Max).

Since I need the minimum of the maxima I thought to scale down the domain of the lists whenever I find a valid list with a maximum less than the original one. For example if I have N=4 the elements of the list will be in 1..8. Let's say I get two lists List1 and List2 with maximum 8 and 7 respectively. Now I have that every other valid list that contains 8 will be rejected since I have found List2 with the maximum = 7 that is less than 8. So my idea is to reset the range of the domain every time I find a maximum less than the previous. For example if the current domain is 1..Max1 and then I find Max2 < Max1 then I will set the domain to 1..Max2.

Is it possibile to do this?

With ECLiPSe you can do this because it has predicates like dvar_domain/2, dvar_update/2. I don't think there are also the same predicates available in SWI (at the least, i didn't find it on manual). — damianodamiano

jschimpf jschimpf · Accepted Answer · 2018-01-20T12:37:30

The idea that you describe is what branch-and-bound algorithms do: you prune those parts of the search that cannot possibly lead to a better solution than the best one you have found so far. Constraint solvers normally provide this functionality in some form.

For example, in ECLiPSe, this is provided by library(branch_and_bound), and you would formulate your problem like

:- lib(ic).
:- lib(branch_and_bound).

min_of_max(N, Max) :-
    length(Xs, N),
    Xs #:: 1..2^(N-1),
    constrain(Xs),
    Max #= max(Xs),
    bb_min(labeling(Xs), Max, _).

By wrapping the bb_min/3 call around the labeling/1 search routine, any attempt to create a list whose maximum is greater or equal than the smallest maximum found so far will lead to failure. By default, this is achieved by dynamically reducing the upper bound of Max (similar to the procedure you outlined in your question), but other strategy-options are available.

Change list domain swi-prolog clpfd

1 Answers