
## 3.2 Relsoftcumulativesum Constraint

Definition 11 RelSoftCumulativeSum *augments* RelSoftCumulative with an integer variable **cost***. It enforces:*
- *C1 and C2 (see* **Definition 2***), and C4 (see* **Definition 10**).

- *The following constraint:* cost =Pj∈J **costV ar**[j]
Sweep based global lower bound. **as for the** SoftCumulativeSum **constraint presented**
in section 2.2.2, a lower bound for the cost **objective variable is given by summing the** lower bounds of all variables in costV ar**, without any increase in complexity in the sweep**
algorithm.

$$L B_{1}=\sum_{j\in\mathcal{J}}m i n(D(c o s t V a r[j]))$$

Interval based global lower bound. **The task interval energetic reasoning presented in**
section 2.2.2 remains the same, except the evaluation of the quantity lb1**, which corresponds**
to over-loads expressed by variables in costV ar **array (see definition 8).**
Within the filtering algorithm of the SoftCumulativeSum constraint, lb1 **is the sum of**
min(costV ar[t]) over all points int time t **within each considered interval, providing that, in**
the implementation, all variables in costV ar array are updated before computing lb1**. With**
respect to the RelSoftCumulative constraint, by definition 11, if mult **is greater than or**
equal to two then it is not possible to evaluate at each point in time t **the exact over-load**
at t. Under-estimating lb1 **would be false because this leads to a over-estimation of task**
interval based lower bounds (see Definition 9).

Therefore, we compute an over-estimation of lb1**, the tightest possible according to the**
definition of the constraint. Notation 4 Let I = [**a, b**] *be an interval of points in time included in* [0, m[, and the set of indexes for intervals in time J = {0, 1, . . . , ⌈m/mul⌉ − 1}*. For each* j ∈ J, \#(**I, j**) *is the* number of time points in common between the range indexed by j and I:
\#(I, j) = |[a, b] ∩ J (j)| We can now reformulate Definition 8 for the RelSoftCumulative. The idea is to evaluate for each J (j) intersecting the current interval I(ai,aj )**, the minimum value between**
min(D(costV ar[j])) and the maximum possible over-load in I ∩ J (j**), which is equal from**
Definition 11 to \#(I, j) ∗ (max(D(costV ar[j])) − ideal **capa**).

Definition 12 Let I(ai,aj) *be a task interval, and* J = {j ∈ J , \#j(I(ai,aj)) > 0}.

lb1 =X
j∈J
min(min(D(costV ar[j])), \#(I, j) ∗ (max(D(costV ar[j])) − ideal **capa**))

## 4 Conclusion

This report proposed several filtering procedures for a global Cumulative **constraint which**
is relaxed w.r.t. to its capacity at some points in time. We provided the extension of our global constraint for the case where side constraints are related **to ranges in time which are** larger than one time unit.