# clpBNR: global_minium for integers

@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?

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

Thanks, that explains it. Appreciate it.

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

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