Re: maximum finite domain constraint for eclipse

Hi,

On a special note to the list. I don't know what is the policy about posts
and so I am not sure if this kind of post fits in. If not, please inform me
and I won't forward such things again. The only reason why I forwarded this
was thinking of anyone else who might want a version of the max constraint
implemented.

On Thu, Feb 01, 2001 at 09:16:47AM +0100, Tobias Müller wrote:
> Dear Rui,
Hello Tobias,

> 
> Warwick Harwey told me that you would have an efficient implementation of a maximum fd constraint
> for eclipse, i.e., the constraint Z#=max(X,Y). I am doing benchmarks with eclipse and would like to
> produce "realistic" results. Can have a copy of your implementation which is most probably the
> fastest around?

You were misinformed, I was asking if Eclipse had a max fd constraint. I
didn't have one.

Anyway, as it is a nice exercise, here goes an implementation of one. I
am not sure if it is the best and most efficient, as I am a newbie in Eclipse.

Anyway, it uses interval propagation and only wakes when the specified
variables have their contributing min ou max updated. Some optimizing quirks
were made for the special cases of nonoverlapping variables and bound ones.

Here goes:

% maxfd(A, B, M) behaves as M #= max(A, B)

maxfd(A, B, M):-
	nonvar(A),
	nonvar(B), !,
	M is max(A, B).
maxfd(A, B, M):-
	nonvar(A), !,
	dvar_domain(B, DomB),
	dom_range(DomB, MinB, MaxB),

	Min is max(A, MinB),
	Max is max(A, MaxB),

	M::Min..Max,

	(nonvar(M) ->
		true
	;
		suspend(maxfd(A, B, M), 3, B -> constrained)
	),
	wake.
maxfd(B, A, M):-
	nonvar(A), !,
	dvar_domain(B, DomB),
	dom_range(DomB, MinB, MaxB),

	Min is max(A, MinB),
	Max is max(A, MaxB),

	M::Min..Max,

	(nonvar(M) ->
		true
	;
		suspend(maxfd(A, B, M), 3, B -> constrained)
	),
	wake.
maxfd(A, B, M):-
	dvar_domain(A, DomA),
	dvar_domain(B, DomB),
	dom_range(DomA, MinA, MaxA),
	dom_range(DomB, MinB, MaxB),

	(MinA > MaxB ->
		A #= M
	;
	 MinB > MaxA ->
	 	B #= M
	;
		Min is max(MinA, MinB),
		Max is max(MaxA, MaxB),

		M::Min..Max,

		suspend(maxfd(A, B, M), 3, (A, B) -> constrained)
	),
	wake.


--Rui