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

From: Benoit Hoessen <b.hoessen_at_gmail.com>
Date: Fri, 26 Feb 2010 08:57:24 +0100
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.

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.

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


Benoit Hoessen


2010/2/25 Kish Shen <kisshen_at_cisco.com>:
> Benoit Hoessen wrote:
>>
>> Hello,
>>
>> I am currently learning to use eclipse and I'm facing a problem. I
>> have a list of couples that needs to be ordered according some
>> constraints. I tried the following model:
>>
>> ArrayCouples is the array of my couples [Couple0, Couple1, ... ]
>> NbCouples is the number of couples
>> OrderedList is a list of integers where each integer represent the
>> index of a Couple in ArrayCouples. Those integers are the variables of
>> my problem and their domain is [0..NbCouples - 1]
>>
>> And the constraints should be (with a c-like syntax)
>> for (i = 0 ; i < NbCouples-2; i++){
>>    CoupleA = ArrayCouples[i];
>>    CoupleB = ArrayCouples[i+1];
>>    //constraint on the element of CoupleA & CoupleB
>> }
>>
>> But it seems that I can't model this with eclipse with my current
>> knowledge or it's not the way I should model my problem.
>>
>> Can somebody tell me what my error is?
>
> Hi Benoit,
>
> It is difficult to give any specific answer, as it is not clear what your
> exact difficult is. You may indeed want to learn more about programming in
> ECLiPSe. Another general comment I can say is that it is probably not a very
> good idea to try and specify the program you want to write in C and then try
> to translate this to ECLiPSe. C does not map very well to ECLiPSe (or Prolog
> in general), and in any case you should be thinking about modelling your
> problem at a higher level...
>
> One possible issue is the data structures you are using: you mention lists
> -- these do not map well to C arrays. ECLiPSe (and Prolog) does provide
> something similar to C arrays -- structures, which allows random access to
> its elements. In addition, ECLiPSe provides syntax that is
> more convenient to use (than what is standard in Prolog), and which also
> looks more like traditional array syntax that you find in C. This array
> notation is described in the manual:
>
> http://www.eclipse-clp.org/doc/userman/umsroot024.html
>
> One issue you should be aware of is the index starts from 1, rather than 0.
>
> On the other hand, for the specific example you show in C, it is not clear
> that you do need random access to the elements, so a list may be the right
> data structure to use. Your example can be dnne in ECLiPSe using a do-loop
> (which is simply a different way of writing recursion, the standard way in
> Prolog to write "loops"):
>
> (fromto(NbCouples, [CoupleA,CoupleB|Rest],[CoupleB|Rest], [_]) do
>    /* constraint on CoupleA and B */
> )
>
> If you also need the index, you can add another iteration specifier like
> count(I,Min,Max).
>
> Cheers,
>
> Kish
>
>
>
> --
> This e-mail may contain confidential and privileged material for the
> sole use of the intended recipient. Any review, use, distribution or
> disclosure by others is strictly prohibited. If you are not the intended
> recipient (or authorized to receive for the recipient), please contact
> the sender by reply e-mail and delete all copies of this message.
> Cisco Systems Limited (Company Number: 02558939), is registered in
> England and Wales with its registered office at 1 Callaghan Square,
> Cardiff, South Glamorgan CF10 5BT.
>
Received on Fri Feb 26 2010 - 07:57:32 CET

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