Re: [eclipse-clp-users] constraint on indexed elements

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Thu, 04 Mar 2010 10:41:49 +1100
Benoit Hoessen wrote:
> Hello,
> 
> First, thank you for your response. I will try to explain better the
> problem I'm trying to solve and the problem I'm facing to model it
> using ECLiPSe. My problem is the following: we have a list of N boxes
> of different sizes but same height. We must create J stacks with those
> boxes. A stack may contain up to 12 boxes. In a stack, the box B can
> be put on box A if the width of A is greater or equals the width of B
> and if the length of A is also greater or equals the length of B.
> 
> My problem is that I don't know how I can model this.
> 
> I tried to following way, but I don't think it's a good way to model it.
> Data:
> * A box is represented with a term: box(Length,Width). The N boxes are
> in a list.
> * A number is associated with the boxes by using a dynamic predicate
> (boxIndex(+I, +B) : is true if B is a box and I is a number) where one
> box is associated with 1 and only 1 number.
> * The J stacks are represented by a list LStacks of length J
> * A stack is represented by a list of length 12
> * A box in a stack is represented by it's number
> Constraints:
> * To model the constraint "up to 12 boxes in a stack", J*12 - N boxes
> of width=length=0 are created. The constraint is now that there will
> always be 12 boxes in a stack
> 
> My problem is to model the constraint on 2 boxes in a stack. I could
> use the suspend library to wait that the 2 variables are instantiated
> to check the satisfaction on the constraint, but I don't like this
> approach as it won't use any domain consistency method.

You can build this kind of constraint yourself with lib(propia):

:- lib(ic).
:- lib(propia).

box_smallereq(I, J) :-
	box_index(I, box(WI, LI)) infers ic,
	box_index(J, box(WJ, LJ)) infers ic,
	WI #=< WJ,
	LI #=< LJ.

box_index(1, box(5,4)).
box_index(2, box(5,2)).
box_index(3, box(7,3)).
box_index(4, box(3,3)).

Example:
?- box_smallereq(I, J), I #=< 2.
I = I{[1, 2]}
J = J{1 .. 3}
There are 3 delayed goals.
Yes (0.00s cpu)


> 
> For me, in a "ideal world" I would'n use the number associated with
> the boxes and the stacks would be represented by variables defined on
> a domain D such that it is the set of the possible boxes. The
> constraint on 2 boxes would be a kind of primitive constraint and as
> it uses only 2 variable, an arc-consistency method could be used.
> The problem is that -as far as I know- symbolic domains in ECLiPSe
> don't accept terms.

The ordering constraint is of course easy in this model:

box_smallereq1(box(WI, LI), box(WJ, LJ)) :-
	WI #=< WJ,
	LI #=< LJ.

but the problem is then to label the positions in the stacks with a
permutation of the available boxes.  I haven't thought about it in
detail, but you could probably use a model where you have variables
that indicate in which stack a particular box is, and use sorted/3
constraints to make sure the stacks are valid.


> 
> Is there a way to get closer to my "ideal world" ?

I think this is a very nice little problem!  I would be interested
to hear suggestions from other users - we could even have a competition
(unless, of course, this is your homework...)


Cheers,
-- Joachim
Received on Thu Mar 04 2010 - 00:40:45 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET