clpBNR: global_minium for integers

Help!
1

@ridgeworks, using clpBNR with the following code:

:- use_module(library(clpBNR)).

distinct([]) .
distinct([X|Xs]):- distinct(Xs,X), distinct(Xs).

distinct([],_).
distinct([X|Xs],Y):- {X<>Y}, distinct(Xs,Y).

sum([],0).
sum([H|T], Sum) :-
   { Sum == H + Sum1 },
   sum(T,Sum1).

Why does the following query fail?

2 ?- length(L,3),L::integer(1,5),distinct(L),  sum(L,S), S::integer, global_minimum(S,Min), enumerate(L).
false.

The following works:

4 ?- length(L,3),L::integer(1,5),  sum(L,S), S::integer, global_minimum(S,Min), enumerate(L).
L = [1, 1, 1],
S = Min, Min = 3.

So my guess is that global_minimum/2 can’t handle <,> and <> for the integer domain? What would be a workaround?

2

The subtle issue here is the semantics of global_minimum/2. The second argument is the minimized (constrained) value of the first argument which is an expression (rather than the expression’s value). So the objective is to define the expression to be minimized; one way is to redefine sum/2:

sum([],0).
sum([H|T], H + Sum1) :- sum(T,Sum1).

then:

?- length(L,3),L::integer(1,5),distinct(L),  sum(L,Sexp), global_minimum(Sexp,Min).
L = [_6676, _6682, _6688],
Sexp = _6676+(_6682+(_6688+0)),
Min = 6,
_6676::integer(1, 4),
_6682::integer(1, 4),
_6688::integer(1, 4).

?- length(L,3),L::integer(1,5),distinct(L),  sum(L,Sexp), global_minimum(Sexp,Min), enumerate(L).
L = [1, 2, 3],
Sexp = 1+(2+(3+0)),
Min = 6 ;
L = [1, 3, 2],
Sexp = 1+(3+(2+0)),
Min = 6 ;
L = [2, 1, 3],
Sexp = 2+(1+(3+0)),
Min = 6 ;
L = [2, 3, 1],
Sexp = 2+(3+(1+0)),
Min = 6 ;
L = [3, 1, 2],
Sexp = 3+(1+(2+0)),
Min = 6 ;
L = [3, 2, 1],
Sexp = 3+(2+(1+0)),
Min = 6 ;
false.

Note that S is an expression in the three list elements rather than an interval value of the sum.

The algorithm underlying global_minimum/2 requires the interval variables in the expression to work. Unfortunately it can be a bit of a trap for the user, as you discovered, but I haven’t yet discovered a better alternative.

1 Like
3

Thanks, that explains it. Appreciate it.

4

Are there options to provide a different search strategy, like clpfd labeling/2 has? e.g.: up, down, bisect, etc

5

The main focus of clpBNR is non-finite domains, i.e., reals, so the provided “labelling” predicates (solve, splitsolve) use bifurcating techniques. But these can also be used on integers. (They actually are hybrid techniques using splitting if the domain is large and ‘enumerate’ if small (interval width less than 16 IIRC).)

enumerate on integer intervals is equivalent to labeling ‘up’. There is currently no ‘down’ but that’s easy to implement yourself, e.g.,

domain(X,integer(L,H)), between(L,H,V), X is L+H-V`

Another dimension to searching is what strategy is used when solving for more than one interval, i.e., labelling order and breadth first vs. depth first. The choices shouldn’t affect the result but can significantly affect the compute time, but it’s problem dependant.

Since the scope for alternatives is broad and there’s nothing preventing users from implementing their own search strategies, I’ve just provided a basic set with the pack. (They’re in the ia_utilities.pl file for those interested in the nitty-gritty.)

3 Likes