clpBNR: difference constraint on reals

@ridgeworks, How do I apply a constraint on reals to assure that A and B are different? As a simple example, suppose that [A,B]::real can have a set of specific real values, let’s say 1.1, 2.1 and 3.1.

How do I express a constraint where A needs to be different than B?
I understand <> is incomplete, but I would expect the following to work:

51 ?- { 1.1 <> 1.1 }.
false. % ok
52 ?- { 1.1 <> 2.1 }.
false. % expected true

What am I missing?

<> is not supported for reals so it implicitly constrains any operands to be integers.

?- {X<>Y}.
X::integer(-1.0Inf, 1.0Inf),
Y::integer(-1.0Inf, 1.0Inf).

The rationale behind the decision was to discourage the use of <> on reals without understanding the implications since it only seems to really apply to finite domains.

However this may suffice, although as an interval constraint it’s pretty weak (doesn’t contribute much to narrowing) :

?- {~(X==Y)}, X=1.1, Y=2.1.
X = 1.1,
Y = 2.1.

?- {~(X==Y)}, X=1.1, Y=1.1.
false.

I tried it, but it doesn’t solve my problem, since I need it to contribute to narrowing:

3 ?- ({ A == 1.1}; { A == 2.1} ), ({ B == 1.1}; { B == 2.1} ), { ~( A == B) }.
A:: 1.100000000000000...,
B:: 1.100000000000000... ;
A:: 1.100000000000000...,
B:: 2.10000000000000... ;
A:: 2.10000000000000...,
B:: 1.100000000000000... ;
A:: 2.10000000000000...,
B:: 2.10000000000000... .
}

The essence of what I need is:

  1. A way to specify a finite set of values (disjoint intervals) for a Variable
  2. A way to constrain two of these variables to be different

is there a way to do this?

First point: a variable is a single interval, not a set of disjoint intervals. But you can use alternative constraints (like you’ve done) to achieve a similar result.

But there’s a second issue here: {A==1.1} doesn’t narrow A to a point value, it’s a (small) interval containing 1.1. Similarly for B. When both are approx. 1.1, you can’t prove ~(A==B)} without further narrowing. But that’s likely not possible within the precision limits of floating point values.

You can get point values for A and B by using rational values like 11r10 and 21r10. Note there’s no point in using constraints when you do this; {A==11r10} is just a very inefficient way of saying A=11r10. Furthermore, applying the ~(A==B)} constraint after A and B are point values is equally pointless (pardon the pun).

So let me rewrite your query as:

?- {~(A==B)}, (A=11r10 ; A=21r10), (B=11r10 ; B=21r10).
A = 11r10,
B = 21r10 ;
A = 21r10,
B = 11r10 ;
false.

Since the floating point values are now outside of the constraint system, this also works:

?- {~(A==B)}, (A=1.1 ; A=2.1), (B=1.1 ; B=2.1).
A = 1.1,
B = 2.1 ;
A = 2.1,
B = 1.1 ;
false.

However, the following doesn’t work because the constraint “compiler” will fuzz the values of A and B:

?- (A=1.1 ; A=2.1), (B=1.1 ; B=2.1), {~(A==B)}.
A = B, B = 1.1 ;
A = 1.1,
B = 2.1 ;
A = 2.1,
B = 1.1 ;
A = B, B = 2.1.

I appreciate this is probably a simplified example of what you’re really trying to do but the details matter. ~(A==B) will only become true when the intervals are non-overlapping and, in general, that may require something like solve to force the issue.

I can easily convert this particular case to the integer domain in clpfd, and use something like:

14 ?- [A,B] ins 21\/11, A #\= B.
A in 11\/21,
A#\=B,
B in 11\/21.

Could this be done in clpbnr?

\/ in clpfd is a union of (possibly) disjoint domains, which is not supported in clpBNR. clpBNR only supports intervals, equivalent to .. in clpfd. I can’t recall the details but I have seen some discussion in the academic literature regarding unions of (real) intervals but the conclusions were inconclusive, i.e., the costs didn’t seem to outweigh the benefits.

Something approximately equivalent to your example in clpBNR:

?- {(A==11r10) or (A==21r10), (B==11r10) or (B==21r10),  ~(A==B)}.
A::real(-1.0Inf, 1.0Inf),
B::real(-1.0Inf, 1.0Inf).

Note that neither clpfd nor clpBNR actually produces values for A and B. For that you need to force the issue by labelling:

?- {(A==11r10) or (A==21r10), (B==11r10) or (B==21r10), ~(A==B)}, solve([A,B]).
A = 11r10,
B = 21r10 ;
A = 21r10,
B = 11r10 ;
false.

Whether this is useful depends on the rest of the problem you’re trying to solve.

I see, so the essence of the limitation is that disjoint intervals are not supported, and therefore we are restricted to point values, which can only be expressed in rational notation or integers.

When you say approximately equivalent, is it because you used the actual rational numbers (not integers) or is there something additional (I already understood that disjoint domains are not supported)?

Using labeling is okay for me, as long as I can use it only at the end when the constraint network has all the constraints. The problem was that I could not find a way to express the discrete values for A and B (because I was using floating points, causing a fuzzed interval to be generated); using or and rationals is what most likely will solve my issue.

I will try it this way (with or and rationals) and report back if I have any problems.

Afterthought

Could not disjoint intervals be supported like this,
e.g A,B ∈ [1,1.5] or A,B ∈ [2,2.5]?:

{ (A>=1, A=<3r2) or (A>=2, A=<5r2), (B>=1, B=<3r2) or (B>=2, B=<5r2), ~(A==B) }.

19 ?- { A==21r10, B==21r10, ~(A == B) }.
A = B, B = 21r10.

19 ?- { A==21r10, ~(A == A) }.
A = 21r10.

20 ?- { A==21r10, ~(A == A) }, solve(A).
A = 21r10.

I would expect false in all of them, is this a bug or am I missing something?

Definitely a bug, but easy to fix. I’m not in a position to push a new release just yet but I can provide instructions for the fix if you’re prepared to edit your copy of clpBNR.

Using boolean constraints this way is somewhat uncharted territory, so I hope nothing else turns up.

No, you’re not restricted to point values, but that was your example (A in 11\/21). I just extended it to a rational number.

Mainly because I used rationals, but also because I haven’t used clpfd enough to definitively say there’s nothing else.

I think that, in general, labelling should only be used after constraints have been defined. Standard Prolog arithmetic is modal (expression evaluation requires that the expression be ground), so it forces you into a “generate (values) and test” paradigm. CLP’s are logical so it encourages a “(apply) test, then generate” paradigm - labelling is part of the generate phase.

Suppose there are two non-overlapping intervals (including point values), V1 and V2. Then we can use them to define A and B:

?- V1::real(1,1.5),V2::real(2,2.5),{((A==V1) or (A==V2)), ((B==V1) or (B==V2)), ~(A==B)}.
V1::real(1, 1.5000000000000002),
V2::real(2, 2.5000000000000004),
A::real(-1.0Inf, 1.0Inf),
B::real(-1.0Inf, 1.0Inf).

The problem here is that the constraints are satisfied without really forcing a solution. Using solve on A and B tries to find small intervals of A and B that meet the constraints (narrowing V1 and V2 in the process) but there are many such possibilities in continuous intervals, so I don’t think that’s really helpful.

To overcome this, since there are two known outcomes, introduce a boolean whose value (0 or 1) dictates the outcome and then enumerate the boolean:

?- V1::real(1,1.5),V2::real(2,2.5),{(T -> ((A==V1) and (B==V2))), (~T -> ((A==V2) and (B==V1)))}, enumerate(T).
T = 0,
V1::real(1, 1.5000000000000002),
V2::real(2, 2.5000000000000004),
A::real(2, 2.5000000000000004),
B::real(1, 1.5000000000000002) ;
T = 1,
V1::real(1, 1.5000000000000002),
V2::real(2, 2.5000000000000004),
A::real(1, 1.5000000000000002),
B::real(2, 2.5000000000000004).

I think this satisfies the requirements of your specific example, but it doesn’t seem very elegant or obvious to me. Furthermore it begs the question of how the non-overlapping V1 and V2 intervals are produced in the first place.

So more thought required. Any idea how clpfd deals with this when the disjoint domains contain more than one value, e.g., 8..10\/20..23 ?. Labelling would just seem to generate a number of point solutions, but maybe that’s good enough. (Do A and B have to belong to different sub-domains?)

I think this is a useful method to work around the limitation of not supporting dijoint intervals, but it has some problems:

  • It does not include the cases {A==V1 and B ==V1 } or {A==V2 and B == V2}, to solve this you could introduce yet another boolean variable and enumerate both of them, but soon you have combinatorial explosion (in the expression) as more intervals are added.

clpfd supports a union of ranges in the definition of the domain of the variable (i.e. your :: operator), dealing with them properly at the time of ‘declaring’ the domain, before constraints are applied. This is what I am missing in clpbnr. Some examples:

19 ?- A in 1..3\/2..5. 
A in 1..5.          % proper handling of intersecting domains
20 ?- A in 1..3\/8..10.
A in 1..3\/8..10.   % proper support of disjoint ranges
24 ?- A in 1..3\/8..10\/2..9\/12..13.
A in 1..10\/12..13. % and a combination of all of the above

Notice this all happens before applying constraints, in the declaration of the domain. The constraints then can only narrow the possible values within the domain, but never expand it.

For clpbnr I was not thinking of generic support for disjoint intervals in constraints, but rather for the initial domain of the variables. Following the above example, something like this:

?- A::[real(1,3), real(2,5)].
A::real(1,5).                             % automatic calculation of the union
?- A::[real(1,3), real(8,10)].
A::[real(1,3),real(8,10)].                % disjoint intervals in the domain
?- A::[real(1,3), real(8,10),real(2,9),real(12,13)].
A::[real(1,10),real(12,13)].              % both of the above
?- A::[real(21r10,21r10),real(11r10,11r10)].
A::[real(11r10,11r10),real(21r10,21r10)]. % disjoint point values
?- A::[11r10,21r10].                      % syntactic sugar for the above
A::[real(11r10,11r10),real(21r10,21r10)]. % perhaps automatically narrow to point value

Where the members of the list would have to be all either integer(L,H) or real(L,H).

There would be no extra cost if the domain was just one interval. The only cost would be the simple and fast check to see if the list has only one interval.

The more significant (performance) cost would only be added if there was more than one range in the original domain, which is perfectly reasonable to me.

But there is no difference between A::real(1,10) and {A>=1,A=<10}:

?- A::real(1,10).
A::real(1, 10).

?- {A>=1,A=<10}.
A::real(1, 10).

?- {(1=<A) and (A=<10)}.
A::real(1, 10).

They’re exactly the same constraint on A (an attributed variable). There is nothing special about the “time of declaring” - constraints can be defined in any order.

But there is no equivalent of clpfd’s union of (sub)domains (intervals with holes), and providing them does require “generic support for disjoint intervals in constraints” because that’s really all there is. Furthermore the combinatorial explosion you referred to using an explicit boolean equally applies here, e.g., a binary operation on two intervals, each with two sub-domains possibly yields an interval with 4 sub-domains. And with continuous domains, there’s no practical limit on the number of sub-domains, no matter how narrow the union is.

Given this it’s very unlikely that unions of sub-domains will be “generically supported”. Furthermore, I haven’t seen any support for disjoint intervals in comparable systems supporting continuous domains (Numerica, Newton, CLIP, to name a few) so I’m even more wary of going down that path.

The question I would like to answer is whether something roughly equivalent could be accomplished within the current conceptual framework of Prolog+clpBNR although possibly not as elegantly as clpfd.

One possible interpretation of A::[real(1,3), real(8,10)]. is:

?- A::real(1,3) ; A::real(8,10).
A::real(1, 3) ;
A::real(8, 10).

This really just maps disjoint domains to Prolog disjunction with choices handled via standard backtracking. Note that this doesn’t necessarily have to be done before A is otherwise constrained:

?- B::real(0,10), {A==B+2}, (A::real(1,3) ; A::real(8,10)).
B::real(0, 1),
A::real(2, 3) ;
B::real(6, 8),
A::real(8, 10).

or equivalently:

?- B::real(0,10),{A==B+2}, ({A>=1,A=<3} ; {A>=8,A=<10}).
B::real(0, 1),
A::real(2, 3) ;
B::real(6, 8),
A::real(8, 10).

The next question is whether some or all of this can be pushed into the clpBNR constraints using boolean operations and, if so, what’s the advantage of doing so. I’m thinking along the lines of:

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}.
X::real(-1.0Inf, 1.0Inf).

This is a perfectly good constraint but the weakness here is that until one of the or terms becomes false, nothing narrows (not even to the bounds of the “union”). But when that occurs, the constraint becomes active:

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}, {X=<5}.
X::real(1, 3).

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}, {X>=5}.
X::real(8, 10).

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}, X::real(5,6).
false.

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}, X::real(2,9).
X::real(2, 9).

?- {((1=<X) and (X=<3)) or ((8=<X) and (X=<10))}, X::real(2,7).
X::real(2, 3).

So this seems to be an adequate way to constrain an interval to a union of sub-domains. However local propagation is inadequate to drive any narrowing (or is weak); additional constraints, perhaps via labelling of some kind, are required. Maybe there’s a way of strengthening this but it’s not immediately obvious to me.

I also think clpfd’s effectiveness in dealing with disjoint domains has little to do with how they’re “declared”. Rather it’s due to clpfd’s “generic support” , i.e., I’m pretty sure A in 1..5, A#\=3 will result in the domain of A becoming disjoint. And B#=A+1 will subsequently define a disjoint domain for B. So I’m still interested in a clpfd solution to your problem and what answers you would deem acceptable.

One of clpfd’s strengths IMO is its ability to deal with “holes” in domains but it’s not something that can be easily ported to continuous (non-finite) domains. If you have a problem that can be easily expressed using disjoint sub-domains in clpfd, why wouldn’t you do that?

The reason is because I see a tremendous potential to use clpBNR in a new way: mixed domains clp, where you have expressions that mix boolean, integer and real constraints. This is very good, because the original domain of the application problem can be much closer to the model of the problem in clp.

Problems (in the real domain) that can be mapped to the integer domain would not need to be mapped, and problems that have both integer and real components (and maybe even boolean) could be expressed in one constraint network.

My suspicion about this potential was verified when some of your workarounds included using boolean expressions in ‘somewhat uncharted territory’. I think there is much more potential here than what meets the eye at first glance; but I can understand if you just want to keep it primarily for the real domain.

If clpBNR can’t handle the real domain effectively, there’s really no point. But as you point out it’s arguably advantageous to handle mixed domains (integers being a subset of reals) and, as long as that doesn’t compromise the primary objective, I’d like to do that. But I can’t see a way of directly supporting unions of sub-domains (like clpfd does) without compromise. I also think there are potentially lots of useful integer and mixed domain problems that can be addressed within the current architecture.

That said, I’d like to explore ways of addressing such unions within the current framework. As previously stated, I think you can express these as constraints using boolean operators. The problem is that local propagation using “or” is too weak and there isn’t a labelling technique to drive the selection of the sub-domains without explicitly introducing booleans just for that purpose (and then enumerating them).

But there are already boolean values in the constraint network that serve this purpose; there’s just no way of getting at them using the accessible intervals (.e.g., A and B). One possible approach is to add a new labelling predicate. I’m not sure what to call it so how about enumerate_domains as a placeholder. It might be used something like:

?- {((1=<A) and (A=<3)) or ((8=<A) and (A=<10))}, clpBNR:enumerate_domains(A).
A::real(1, 3) ;
A::real(8, 10).

If there are no “sub-domains”, it does nothing:

?- A::real(1,3), clpBNR:enumerate_domains(A).
A::real(1, 3).

With two such intervals:

?- {((1=<A) and (A=<3)) or ((8=<A) and (A=<10)), ((1=<B) and (B=<3)) or ((8=<B) and (B=<10))}, clpBNR:enumerate_domains([A,B]).
A::real(1, 3),
B::real(1, 3) ;
A::real(1, 3),
B::real(8, 10) ;
A::real(8, 10),
B::real(1, 3) ;
A::real(8, 10),
B::real(8, 10).

I’m not sure how well this scales; it depends on finding any intervals in the network which are an argument in an or constraint that can affect the interval in question. Furthermore the network is a graph so you have to detect cycles.

Getting back to the original problem, the other stated requirement was that ~(A==B). The problem here is that it can’t be applied as an initial constraint, i.e., before the A and B sub-domains have been enumerated, since it will immediately fail (at that point A==B is true). It must be applied as a post-labelling constraint:

?- {((1=<A) and (A=<3)) or ((8=<A) and (A=<10)), ((1=<B) and (B=<3)) or ((8=<B) and (B=<10))}, clpBNR:enumerate_domains([A,B]), {~(A==B)}.
A::real(1, 3),
B::real(8, 10) ;
A::real(8, 10),
B::real(1, 3) ;
false.

This is a bit unfortunate, but maybe it’s good enough.

So I currently see two possibilities (other than Prolog disjunction): explicit booleans or an additional labelling predicate, e.g., enumerate_domains.

This is what I don’t see, in other words, I don’t see why it adds much compromise. Right now you have the following:

attr_unify_hook(IntDef, Num) :-         % unify an interval with a numeric
	number(Num),
	IntDef = interval(Type,(L,H),Nodelist,Flags),
	(Type=integer -> integer(Num) ; true),   % check that Num is consistent with Type
	L=<Num, Num=<H, !,                       % and in range
	(debugging(clpBNR,true) -> monitor_unify_(IntDef, Num) ; true),
	linkNodeList_(Nodelist, T/T, Agenda),
	stable_(Agenda).                    % broadcast change

attr_unify_hook(interval(Type1,V1,Nodelist1,Flags1), Int) :-   % unifying two intervals
	get_attr(Int, clpBNR, interval(Type2,V2,Nodelist2,Flags2)),  %%SWIP attribute def.
	mergeType_(Type1, Type2, NewType),  % unified Type=integer if either is an integer
	^(V1,V2,V), !,                      % unified range is intersection (from ia_primitives),
	mergeNodes_(Nodelist2,Nodelist1,Newlist),  % unified node list is a merge of two lists
	mergeFlags_(Flags1,Flags2,Flags),
	(debugging(clpBNR,true) -> monitor_unify_(interval(Type1,V1,_,Flags), Int) ; true),
	% update new type, value and constraint list, undone on backtracking
	put_attr(Int,clpBNR,interval(NewType,V,Newlist,Flags)),
	linkNodeList_(Newlist, T/T, Agenda),
	stable_(Agenda).                    % broadcast change

attr_unify_hook(interval(Type,Val,Nodelist,Flags), V) :-   % new value out of range
	g_inc('clpBNR:evalNodeFail'),  % count of primitive call failures
	debugging(clpBNR, true),       % fail immediately unless debug=true
	debug_clpBNR_('Failed to unify ~w::~w with ~w',[Type,Val,V]),
	fail.

Why not add two new interval types (besides integer and real): union_integer and union_real. They contain a list of (disjoint) real or integer intervals.

then you add new unification hooks like this:

attr_unify_hook(interval(union_integer,IntIntervalList,Nodelist1,Flags1), Interval) :-
   % handle each 'sub-interval' with the same code used for 
   % one 'integer' interval backtracking to solve the next sub-interval
   ...

attr_unify_hook(interval(union_real,RealIntervalList,Nodelist1,Flags1), Interval) :-
   % handle each 'sub-interval' with the same code used for 
   % one `real` interval backtracking to solve the next sub-interval
   ...

The union_real and union_integer intervals would be created using the notation I mentioned above: e.g. A::[real(1,3),real(5,8)], or better: A::real([(1,3),(5,8)]. If the intervals intersect, the code that handles this syntax would take care of converting the expression into a set of disjoint intervals (or into a single interval if that is the case).

I fail to see why the approach above compromises the system. There is very little performance penalty, and there is no need to modify any of the constraint code. The above code would provide what clpfd does but extending it to reals. Maybe I am crassly missing something here?

No it wouldn’t. In fact that code fragment only addresses unification of intervals, which is a small piece of the puzzle. It may (partially) define a container for a union of interval sub-domains, but it doesn’t define any operations on those containers. It’s analogous to defining a vector as an array of numbers, but not providing the the vector function library. The equivalent to such a library in clpBNR is the 700+ lines of Prolog implementing the relational interval arithmetic primitives.

Consider “A==B+C” where A, B, and C are unions of length lA, lB, and lC respectively. “B+C” yields a union of possibly lB * lC subdomains (maybe less?) and this has to be intersected with the lA subdomains of A. Since this a relation, now you have to calculate A-C and intersect this with B. And similarly for 'C==A-B`, all within the same primitive operation. That’s considerably more complicated than the 6 arithmetic evaluations (2 bounds for each of 3 intervals) required to implement the same relation on simple intervals.

Non-monotonic primitives like Y==abs(X) and Y==X**2 and the repeating trig primitives would require special attention because they may produce a union from a single interval.

These multiple piecewise and intersection calculations are considerably more complex (and costly) than the simple interval/intersection case.

In addition, most of the utility predicates (solve, enumerate, global_minimum) would need to be adapted (if possible) or new versions produced.

I hope you see why this just isn’t so. It’s certainly not a feature I would undertake without evidence of a significant payback. And so far, I haven’t seen any.

This thread got somewhat side tracked into a discussion of mechanics, so for the record:

For finite domains (integers) clpBNR provides equivalent semantics to clpfd. As a proof of concept, here’s a predicate which maps a clpfd domain expression (X in Dom) to clpBNR constraints:

fd_BNR(X in N) :- integer(N), !, X=N.
fd_BNR(X in L..H) :- !, X::integer(L,H).
fd_BNR(X in Dom) :-
    fd_map_domains(Dom,X,1.0Inf,-1.0Inf,Min,Max,Cs),
    X::integer(Min,Max),
    {Cs}.

fd_map_domains(D1\/D2,X,MinIn,MaxIn,Min,Max,(Cs or C)) :- !,
    fd_map_domains(D1,X,MinIn,MaxIn,Min1,Max1,Cs),
    fd_map_domains(D2,X,Min1,Max1,Min,Max,C).
fd_map_domains(D1,X,MinIn,MaxIn,Min,Max,C) :-
    fd_map_domain(D1,X,Min1,Max1,C),
    Min is min(MinIn,Min1),
   Max is max(MaxIn,Max1).

fd_map_domain(L..H,X,L,H,(Xl=<X,X=<Xh)) :- !,
    Xl is min(L,H), Xh is max(L,H).
fd_map_domain(N, X,N,N, X==N).

A clpfd query:

?- X in 8..10\/1..3, label([X]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 8 ;
X = 9 ;
X = 10.

and using fd_BNR:

?- fd_BNR(X in 8..10\/1..3), enumerate(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 8 ;
X = 9 ;
X = 10.

The clpfd query:
?- X in 8..10\/1..3, Y in 8..10\/1..3, X#\=Y, label([X,Y]).
is equivalent to:
?- fd_BNR(X in 8..10\/1..3), fd_BNR(Y in 8..10\/1..3), {X<>Y}, enumerate([X,Y]).

Now the original post questioned whether this be extended to the continuous domain of reals? And it can to a limited degree. The constraints themselves are fine and will be imposed on any solution. However, in the limited context of this last example there are two problems.

First, “’<>’” has no sound meaning in the real domain. (For this reason clpBNR restricts its use to integers.)

Second, you can’t “enumerate” a set of reals which has an infinite number of members. So to find solutions, you need to rely on additional constraints and/or search mechanisms relevant to the specific problem. For the simple case where a real can only have a relatively small number of discrete values, the best approach would seem to be a custom labelling predicate which generates them. When X and Y are point values, the constraint {~(X==Y)} can be used for inequality.

Note that neither clpfd or clpBNR has any direct support for the notion of subdomains, e.g., inequality of subdomains can’t be expressed. But internally clpfd can represent domains with “holes” so it should be more efficient for those fd problems with sparse domains.

2 Likes

I think we are talking about two different use cases:

  1. Provide generic disjoint interval support, for which constraints operations would produce new intervals, etc.
    ** This of course, would require rewriting everything as you rightly mention; the use case I had in mind was much more simple:
  2. Provide simple pre-defined (ground) disjoint domain support. e.g. Variables can be limited, at the time you ‘declare’ their intervals, to disjoint (ground) intervals. This is very different from complete support for operations on disjoint intervals, that is what my code example solved.
    ** With this use case complete support for interval operations is not needed, the only thing that is needed is that values not present in the original domain (with disjoint intervals) are discarded as early as possible. This is what the unification code above would achieve.

I can see that use case 2 would not be interesting from a mathematical point of view (because it doesn’t provide support for operations on disjoint intervals), but it is quite useful to solve practical problems (e.g. a truck can only be in two/three/…n disjoint ranges of latitude/logitude + plus a number of constraints for cost, speed, etc ).

This description is still a bit hypothetical to be specific, but I would model this by defining an integer variable, e.g., R, ranging from 1 to n and using boolean constraints to associate region values to lat/long ranges, like in this example (I’m using a development system which supports “,” as a synonym for “and”):

regions(R,Lat,Long) :-
	R::integer(1,4),
	{(R==1, 33.5=<Lat,Lat=<37.1, 11.6=<Long,Long=<13.3) or
	 (R==2, 36.1=<Lat,Lat=<40.4, 15.6=<Long,Long=<17.8) or
	 (R==3, 41.5=<Lat,Lat=<44.0, 10.1=<Long,Long=<11.9) or
	 (R==4, 44.6=<Lat,Lat=<47.7, 12.6=<Long,Long=<14.4)
	}.

This defines the lat/long limits for each R value. Solutions can be generated by enumerating R values - simple because they’re a limited set of integers:

?- regions(R,Lat,Long), enumerate(R).
R = 1,
Lat::real(33.49999999999999, 37.10000000000001),
Long::real(11.599999999999998, 13.300000000000002) ;
R = 2,
Lat::real(36.099999999999994, 40.400000000000006),
Long::real(15.599999999999998, 17.800000000000004) ;
R = 3,
Lat::real(41.49999999999999, 44.00000000000001),
Long::real(10.099999999999998, 11.900000000000002) ;
R = 4,
Lat::real(44.599999999999994, 47.70000000000001),
Long::real(12.599999999999998, 14.400000000000002).

It works “backwards” to solve for R from a Lat and Long:

?- regions(R,Lat,Long),Lat=37,Long=16.
R = 2,
Lat = 37,
Long = 16.

And multiple trucks could be forced to occupy different regions by ensuring their region values were distinct.

I’m not understanding why these kinds of mixed mode solutions don’t apply to “practical problems” of the sort you’re interested in.

1 Like

Just as an examle, suppose the trucks use solar panels for some of its energy, and you have constraints and functions that depend on the specific (real number) lat/long.

In this case it is not useful to divide it into ‘regions’ (mapped to integers), you need the actual real lat/long within the region to apply all the other constraints/functions related to the solar panel.