# cumulative predicate

From: Krzychu Świdziński <kanibalus_at_o2.pl>
Date: Thu 06 Oct 2005 04:17:56 PM GMT
Message-ID: <43454E34.3060503@o2.pl>
```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:

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
· Ends, if different from the symbol unused, corresponds respectively to
the finishing dates Fi of tasks Oi, 1£i£n; in consequence the following
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
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
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
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>
Content-Type: text/plain; charset=UTF-8; formatowed
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
```
Received on Thu Oct 06 17:21:18 2005

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:39 PM GMT GMT