cumulative predicate

Helo,


Could anybody gave me an example how to use cumulative/4 or cumulative/5 
predicate???. Or mabye you have idea how to fix my problem. I tried to 
translate easy program written in CHIP Constraint Logic Program, but I 
fail.
We have 7 tasks, we know durations time for the tasks and also a list of 
resource uages by tasks. It looks like this:

task duration time resource used by tasks
1 16 2
2 6 9
3 13 3
4 7 7
5 5 10
6 18 1
7 4 11

We want to know what's the start time for every task, minimum ending 
time for all tasks, and we can't use more then 13 resources at the same 
time.
In CHIP program looks like this:

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

top:-
LS = [S1,S2,S3,S4,S5,S6,S7], % start times
LD = [16, 6,13, 7, 5,18, 4], % duration times
LK = [K1,K2,K3,K4,K5,K6,K7], % ending times
LR = [2,9,3,7,10,1,11], % resurce used by tasks

LS :: 1..100,
Koniec :: 1..100,
LK :: 1..100,
Limit :: 1..13, %we can't use more then 13 resources at the sime time

cumulative(LS, LD, LR, LK, unused, Limit, Koniec, unused),
min_max(labeling(LS),End),

write('LS = '), writeln(LS),
write('LD = '), writeln(LD),
write('LK = '), writeln(LK),
write('LR = '), writeln(LR),
write('Limit = '), writeln(Limit),
write('End = '), writeln(End).

labeling([]).
labeling([X|Y]):-
indomain(X),
labeling(Y).
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 

******************************************************************
Solution is:

LS=[ 1,17,10,10, 5, 5,1]
LD=[16,6,13,7,5,18,4]
LK=[17,23,23,17,10,23,5]
LR=[2,9,3,7,10,1,11]
Limit=13
End=23

******************************************************************
Description of CHIP's cumulative/8 predicate:

cumulative(+Starts, +Durations, +Resources, +Ends, +Surfaces,+High, 
+End, +IntermediateVal)
Summary: A cumulative resource constraint
Arguments:
+Starts A non empty list of integers or domain variables
+Durations A non empty list of integers or domain variables
+Resources A non empty list of integers or domain variables
+Ends The symbol unused or a non empty list of integers or domain variables
+Surfaces The symbol unused or a non empty list of integers.
+High An integer or a domain variable
+End The symbol unused or an integer or a domain variable
+IntermediateVal The symbol unused or a list [Middle, Surface] with an 
integer Middle and a domain variable Surface

The value unused specifies that an optional argument is not used.
System: Finite Domain Constraint
Description:
The cumulative constraint cumulative/8 can be applied to a broad range 
of applications. In order to explain the semantics of its parameters we 
can take as an example its application in solving scheduling problems. 
The cumulative constraint expresses the fact that at any instant the 
corresponding total of the resources for the tasks does not exceed a 
given limit.
Assume that n is the number of items for the following lists:
Starts = [O1, ..., On],
Durations = [D1, ..., Dn],
Resources = [R1, ..., Rn],
Ends = [E1, ..., En] or the symbol unused,
Surfaces = [S1, ..., Sn] or the symbol unused;
and let :
a = min(min(O1), ..., min(On)),
b = max(max(O1) + max(D1), ..., max(On) + max(Dn)),
where :
min(X) means the minimum value in the domain of X
max(X) means the maximum value in the domain of X
All parameters which are lists should have the same number of items n.
· Starts corresponds respectively to the start of tasks Oi, 1=<i=<n.
· Durations corresponds respectively to the duration Di of tasks Oi, 
1=<i=<n.
· Ressources corresponds respectively to the amount of resource Ri 
required by tasks Oi, 1=<i=<n.
· Ends, if different from the symbol unused, corresponds respectively to 
the finishing dates Fi of tasks Oi, 1£i£n; in consequence the following 
additional conditions hold:
Any i 1=<i=<n, Oi + Di = Ei
· Surfaces, if different from the symbol unused, corresponds 
respectively to surfaces Si of tasks Oi, 1=<i=<n; in consequence the 
following additional conditions hold:
Any i 1=<i=<n, Di * Ri = Si
For example, if the value of Si is equal to 6 then possible values of 
the pair (Di,Ri) are :
{(1,6), (2,3), (3,2), (6,1)}; (1,6) means task Oi requires 6 units of a 
given resource during 1 unit of time, (2,3) means 3 units of a given 
resource during 2 units of time, etc.
· High corresponds to the upper limit of the amount of resource and 
enforces the following constraints:
Any i 1=<i=<n, Di > 0,
Any i 1=<i=<n, Ri > 0,
Any i a=<i=<b, High = max(Sum Rj), for all j/ j/Oj=<i=<Oj+Dj-1
· End, if different from the symbol unused, corresponds to the global 
end of the schedule and enforces the following constraint:
Any i 1=<i=<n, End = max(Oi + Di) End is an integer or a domain variable.
· IntermediateVal, if different from the symbol unused, should have the 
following form [Middle, Surface]. Surface can be interpreted as the 
surface of the profile resource utilisation which is greater than the 
intermediate value Middle (an integer given by the user). This parameter 
enforces the additional constraint
Any i / a=<i=<b, Surface = Sum(max(0, SumRj - Middle)), for all j/ 
Oj=<i=<Oj+Dj-1
IMPORTANT: If the call of the cumulative constraint, cumulative/8, 
contains ground values and especially when High, End and Surface are 
ground values (integers); then the additional constraints are enforced:
· the maximum resource utilisation profile is equal to High;
· the effective general end is equal to End;
· the surface of top of the intermediate value Middle is equal to
Surface.
In general, the following variables are domain variables :
High :: 0..MaxH,
End :: 0..MaxE,
Surface :: 0..MaxS,
and they enforce the following conditions :
· the maximum resource profile utilisation is not greater than MaxH,
· the effective general end is not greater than MaxE,
· the surface on top of the intermediate value Middle is not greater
than MaxS.

Choice point: No.
Fail Conditions: The constraint fails if no values in the domains of the 
variables can satisfy the conditions. It can fail before all variables 
are ground, either when the constraint is stated or when it is woken up 
dFrom owner-eclipse-users@icparc.ic.ac.uk Fri Oct 07 12:11:15 2005
Received: from majordomo by typhoon.icparc.ic.ac.uk with local (Exim 4.51)
	id 1ENq26-0001tf-JM
	for eclipse-users-outbound@icparc.ic.ac.uk; Fri, 07 Oct 2005 12:04:58 +0100
Received: from tempest.icparc.ic.ac.uk ([155.198.177.95] helo=icparc.ic.ac.uk)
	by typhoon.icparc.ic.ac.uk with esmtpsa (TLSv1:AES256-SHA:256)
	(Exim 4.51)
	id 1ENq25-0001tY-Qx
	for eclipse-users@icparc.ic.ac.uk; Fri, 07 Oct 2005 12:04:57 +0100
Message-ID: <43465659.9090603@icparc.ic.ac.uk>
Date: Fri, 07 Oct 2005 12:04:57 +0100
From: Joachim Schimpf <j.schimpf@icparc.ic.ac.uk>
Organization: IC-Parc, Imperial College London
User-Agent: Mozilla/5.0 (X11; U; SunOS sun4u; en-GB; rv:1.4) Gecko/20030701
X-Accept-Language: en, en-us
MIME-Version: 1.0
To:  eclipse-users@icparc.ic.ac.uk
Subject: Re: [eclipse-users] cumulative predicate
References: <43454DB3.6060103@o2.pl> <43454E34.3060503@o2.pl>
In-Reply-To: <43454E34.3060503@o2.pl>
Content-Type: text/plain; charset=UTF-8; formatowed
Content-Transfer-Encoding: 8bit
X-SA-Do-Not-Run: Yes
Sender: owner-eclipse-users@icparc.ic.ac.uk
Precedence: bulk
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Mail-From: owner-eclipse-users@icparc.ic.ac.uk
X-SA-Exim-Scanned: No (on typhoon.icparc.ic.ac.uk); SAEximRunCond expanded to false

Krzychu Świdziński wrote:
> Helo,
> 
> 
> Could anybody gave me an example how to use cumulative/4 or cumulative/5 
> predicate???. Or mabye you have idea how to fix my problem. I tried to 
> translate easy program written in CHIP Constraint Logic Program, but I 
> fail.

Why don't you show us the translation you tried?

By the way, the CHIP program you posted will not work either,
unless CHIP speaks Polish and knows that Koniec is meant to
be the same variable as End :-)


-- 
  Joachim Schimpf              /             phone: +44 20 7594 8187
  IC-Parc                     /      mailto:J.Schimpf@imperial.ac.uk
  Imperial College London    /    http://www.icparc.ic.ac.uk/eclipse