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

From: Benoit Hoessen <b.hoessen_at_gmail.com>
Date: Fri, 19 Mar 2010 10:59:45 +0100
Hi,

I joined my solution that I made with the suggestion of Joachim
Schimpf. To test it, I use the following command on random generated
data (data.tar.gz)
$ eclipse-clp -e "['stackingProblem.clp'],Ls=[`more
data/data0.dbx`],stack(Ls,St),write(St),nl,halt."

Also, like Thorsten Winterer suggested me, a more efficient approach
would use classes of boxes where a class represent the set of boxes
with the same dimensions.

Benoît Hoessen

2010/3/18 Riyadh Abdulkadir <riyadhabdulkadir_at_gmail.com>:
> Hi everyone,
>
> I found this problem interesting and here is my beginners solution. I
> think that the createstacks/2 clause in particular can be improved. Has
> anyone else given this a go?
>
> % Start of program
>
>
> % Program to arrange boxes in stacks of 12 depending on their width and
> depth
> % A box can be stacked onto another box if the width and depth are smaller
> or equal to the box below
> % Only the minimum number of stacks required is checked, if no valid
> solution is found it does not add more stacks
>
> % A version with only 8 boxes and maximum stack of three boxes finds a
> solution in a short time
> % This version finds a solution quickly, you can rearrange the boxes to make
> it more difficult
>
> :-lib(ic).
> :-lib(lists).
>
>
> %list of 30 boxes
> %argument 1 = box number, argument 2 = width, argument 3 = height
>
> box(15, 31, 31).
> box(16, 30, 30).
> box(17, 29, 29).
> box(18, 28, 28).
> box(19, 27, 27).
> box(20, 26, 26).
> box(21, 25, 25).
>
> box(22, 24, 24).
> box(23, 23, 23).
> box(24, 22, 22).
> box(25, 21, 21).
> box(26, 20, 20).
> box(27, 19, 19).
> box(28, 18, 18).
> box(29, 17, 17).
> box(30, 16, 16).
> box(01, 15, 15).
> box(02, 14, 14).
> box(03, 13, 13).
>
> box(04, 12, 12).
> box(05, 10, 10).
> box(06, 9, 9).
> box(07, 8, 8).
> box(08, 7, 7).
> box(09, 6, 6).
> box(10, 5, 5).
> box(11, 4, 4).
> box(12, 3, 3).
> box(13, 2, 2).
> box(14, 1, 1).
>
> % clause to insert an element into a list - required by permutation clause
>
>
> insert(X, L, L1) :-
> 	delete(X, L1, L).
>
> % creates permutations of a list of items
>
> permutation([], []).
> permutation([X|L], P) :-
> 	permutation(L, L1),
> 	insert(X, L1, P).
>
> % Attempts to add a box to the next box on the list
>
> % Argument 1 is the stack of boxes to be added succesively
> % Argument 2 is the box at the botton of the stack
> % The checkpositions clause sends the first element of the stack as the
> second clause and the rest of % the stack as the first clause
>
>
> addbox([], _).
> addbox([H|T], Boxstack) :-
> 	[S|_] = Boxstack,
> 	box(H, W1, _),
> 	box(S, W2, _),
> 	box(H, _, D1),
> 	box(S, _, D2),
> 	W1 =< W2,
> 	D1 =< D2,
> 	addbox(T, [H|Boxstack]).
>
> % Divides the permutation of the list of boxes into stacks of 12
>
> % The first predicate matches the last stack if it has less than 12 boxes
> % It seems possible to code this in a better way
>
> createstacks(Stack, Stack) :-
> 	length(Stack, N),
> 	N < 12,
> 	N > 0.
> createstacks([B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12|_], [B1, B2,
> B3, B4, B5, B6, B7, B8, B9, B10, B11, B12]).
>
> createstacks([_, _, _, _, _, _, _, _, _, _, _, _|Rest], Stack) :-
> 	createstacks(Rest, Stack).
>
> % Calls addbox for each stack
>
> checkpositions([]) :- true.
> checkpositions([[Sh|St]|T]) :-
> 	addbox(St, [Sh]),
>
> 	checkpositions(T).	
>
> % The stackem clause uses findall to get a list of boxes
> % I them calls permutation to get the first permutaion
> % The second findall createstacks to create a list of all stacks
> % Finally is calls checkpositions to check if each stack is valid
>
>
>
> stackem(Boxes, Stacks) :-
> 	findall(B, box(B, _, _), Boxes),
> 	permutation(Boxes, OrderedBoxes),
> 	findall(Stack, createstacks(OrderedBoxes, Stack), Stacks),
> 	writeln(Stacks),
> 	checkpositions(Stacks).
>
> 	
> % End of program		
> 		
> 	
>
> Regards
> Riyadh
>
>
> On Thu, 2010-03-04 at 10:41 +1100, Joachim Schimpf wrote:
>> 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
>>
>>
>> ------------------------------------------------------------------------------
>> Download Intel&#174; Parallel Studio Eval
>> Try the new software tools for yourself. Speed compiling, find bugs
>
>> proactively, and fine-tune applications for parallel performance.
>> See why Intel Parallel Studio got high marks during beta.
>> http://p.sf.net/sfu/intel-sw-dev
>
>> _______________________________________________
>> ECLiPSe-CLP-Users mailing list
>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
>>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
>



Received on Fri Mar 19 2010 - 09:59:53 CET

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