The balance constraint is a global constraint that can be used to enforce the capacity of a discrete resource or a discrete reservoir.

The balance constraint alone is sufficient to ensure that the minimal and maximal capacity of the resource are enforced, provided that the minimal or maximal capacity of the resource do not vary over time.

Be aware that if the minimal or maximal capacity of the resource does vary over time, then the balance constraint alone is not sufficient and it must be used together with the timetable constraint in order to ensure the soundness of the search.

The balance constraint internally maintains a precedence graph between the time-points (start, end) of the activities on the resource. It propagates by analyzing this graph in order to discover new time bounds for activities as well as new precedence relations between activity time-points.

In general, the balance constraint is useful as soon as there is a significant number of precedence relations between the time-points of the activities on the resource. Note that precedence constraints (for example, IlcActivity::startsAfterEnd) impose such precedence relations.

It is important to note that the memory requirement of the balance constraint is higher than the one of the disjunctive or the timetable constraint because of the internal precedence graph. Furthermore, if n denotes the number of activities on the resource, the worst-case complexity of the balance constraint is in O(n3) and the average complexity is in O(n2). Therefore, the balance constraint should be used for small or medium-size problems, where a strong pruning that exploits precedence relations is required.

The balance constraint internally maintains a precedence graph between the time-points (start, end) of the activities on the resource. More precisely:

The balance constraint algorithm computes the resource level balance just before and just after each vertex in the precedence graph, taking into account the quantity of resource produced or consumed by the vertices that surely and/or possibly execute before the current vertex. It allows one to restrict the domain of the time variables of activities as well as to discover new precedence relations between time-points.

As an example of propagation, consider a very simple scheduling problem with a reservoir with maximal level 2, initial level 0, two temporally ordered producing activities p1 and p2 that produce 2 units of reservoir at their end time-point, and four temporally ordered consuming activities c1, c2, c3 and c4 that consume 1 unit of reservoir at their start time-point. The balance constraint will automatically order all the activities as follows:

end(p1) ≤ start(c1) ≤ start(c2) ≤ end(p2) ≤ start(c3) ≤ start(c4)

The main difference between the balance constraint and the timetable constraint is that the timetable constraint relies on the absolute position of activities in time whereas the balance constraint relies on their relative position. The timetable constraint estimates the resource level at absolute dates, whereas the balance constraint estimates the resource level at nodes of the internal precedence graph, given their relative positioning. In general, these nodes correspond to time-points that are still not instantiated.

One can show that neither of the two global constraints is dominated by the other: both can perform some propagation that the other one would not detect.

Both global constraints require a complex internal structure (the timetable and the precedence graph). For the balance constraint, this internal structure is heavier as it must store the relative position of activities but it allows, in many cases, a stronger propagation than the timetable constraint.

As stated earlier, the balance constraint is sufficient to ensure that any solution on a discrete resource or a reservoir satisfies the resource maximal and minimal capacity constraint (provided that the maximal or minimal capacity of the resource does not vary over time). Thus, it is entirely possible to use the balance constraint alone to enforce the capacity of a discrete resource or a reservoir. Nevertheless, as the balance constraint is more complex than the timetable constraint, it is a good idea to systematically post a timetable constraint whenever a balance constraint is posted. It may allow some additional propagation as well as a global speed up of the propagation.

The balance constraint can be considered as a generalization of the disjunctive constraint for discrete resources and reservoirs.

On a discrete resource, the balance constraint subsumes the disjunctive constraint: everything that is found by the disjunctive constraint will also be found by the balance constraint, but some adjustments are found by the balance constraint that cannot be found by the disjunctive constraint.

Consider an example of a discrete resource of maximal capacity 10, and three activities act1, act2 and act3 of duration 10 that require four units of this discrete resource. The three activities cannot overlap. Suppose that we have the following precedence constraints:

act1.endsAfterStart(act3, 1)
act3.startsAfterStart(act2)
act3.endsAfterEnd(act2)
act2.endsAfterStart(act3, 1)

The balance constraint will discover that activity act1 cannot start to be processed before the end of activity act2. A consequence is that the start time of act1 must be greater than 10. Note that neither the disjunctive constraint nor the timetable constraint on the discrete resource would deduce this adjustment.

To create a balance constraint, use the member function IlcCapResource::makeBalanceConstraint.

Remember that the balance constraint created by one of these member functions must be posted in order to be taken into account.

See Also

IlcDiscreteResource, IlcReservoir.