may exceed the number of time points in I(ai,aj ) multiplied by ideal capa. We can improve LB1**, provided we remove from the computation over-loads yet taken into account in**
the cost variable. In our implementation, we first update variables in costV ar **(by rule 3),**
and compute LB1 to update cost**. In this way, no additional incremental data structure is**
required.

To obtain the new lower bound we need to compute lower-bounds of cost **which are local**
to each interval I(ai,aj ).

Definition 8 lb1(ai,aj ) =Pt∈I(ai
,aj
)
min(D(costV ar[t]))
Then, next proposition is related to the free available number of resource units within a given interval.

Proposition 1 *The number* FreeArea(ai,aj ) of free resource units in I(ai,aj) s. t. no violation is entailed is (max(D(end[aj ])) − min(D(start[ai]))) ∗ ideal **capa**.

Proof: From Definition 7.

From Definition 8 and Proposition 1, FreeArea(ai,aj) + lb1(ai,aj )**is the number of time**
units that can be used without creating any new over-load into the interval I(ai,aj ) **compared**
with over-loads yet taken into account in lb1(ai,aj ).

Definition 9 Inc(ai,aj ) =Pa∈S(ai
,aj
)
W(ai,aj )(a)−FreeArea(ai,aj) − lb1(ai,aj )
Inc(ai,aj )**is the difference between the required energy and this quantity. Even if one variable**
in costV ar **has a current lower bound higher that the value obtained from the profile, the**
increase Inc(ai,aj )**is valid (smaller, see Definition 8). We are now able to improve** LB1.

LB2 = LB1 + max(ai,aj )∈A2 (Inc(ai,aj ))
Another lower bound can be computed from a partition P of [0, m**[ in disjoint intervals**
obtained from pairs of activities (ai, aj ): LB(P ) = LB1 +PI(ai
,aj
)∈P
Inc(ai,aj ). Obviousy LB2 ≤ LB(P )**. However, time complexity of the algorithm deduced from rule 2 in**
the SoftCumulative **constraint is** O(n 2 + n ∗ m**). This complexity should reasonably not**
be increased. Computing LB2 **can be directly performed into this algorithm without any**
increase in complexity.3 Pruning Rule 4 If LB2 > min(D(**cost**)) *then* [min(D(cost))**, LB**2[ *can be removed from* D(**cost**).

Proof: From Definition 7, LB1 is a lower bound of **cost**. Since intervals are disjoint, by Definition 9 the quantity LB(P )is a lower bound of **cost**. LB2 ≤ LB(P ). Therefore LB2 is a lower bound of cost. The pruning rule holds.

Aggregating local violations. **Once the profile is computed, if some activities having a**
null compulsory part cannot be scheduled without creating new over-loads, then LB1 can be augmented with the sum of minimum increase of each activity. This idea is inspired from generic solving methods for over-constrained CSPs, e.g., Max-CSP **[10]. Our experiments** shown that there is quite often a way to place any activity without creating a new violation.

This entails a null lower bound. Therefore, we removed that computation from our implementation. We inform the reader that we described the procedure **in a preliminary technical**
report [11].

3On the contrary, determining a relevant partition P from the activities would force to use an independent algorithm, which can be costly depending on the partition we search for. Finally, we decided to use only LB2.