From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>

Date: Thu, 04 Mar 2010 10:41:49 +1100

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, -- JoachimReceived 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
*