5.198. interval_and_sum
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
A maximum resource capacity constraint: We have to fix the origins of a collection of tasks in such a way that, for all the tasks that are allocated to the same interval, the sum of the heights does not exceed a given capacity. All the intervals we consider have the following form: , where is an integer.
- Example
-
Figureย 5.198.1 shows the solution associated with the example. The constraint holds since the sum of the heights of the tasks that are located in the same interval does not exceed the limit 5. Each task is depicted by a rectangle associated with the interval to which the task is assigned. The rectangle is labelled with the position of within the items of the collection. The origin of task is represented by a small black square located within its corresponding rectangle . Finally, the height of a rectangle is equal to the height of the task to which it corresponds.
Figure 5.198.1. The solution to the Example slot with the use of each interval
- Typical
- Symmetries
Items of are permutable.
One and the same constant can be added to the attribute of all items of .
An occurrence of a value of that belongs to the -th interval, of size , can be replaced by any other value of the same interval.
can be decreased to any value .
can be increased.
- Arg. properties
Contractible wrt. .
- Usage
This constraint can be use for timetabling problems. In this context the different intervals are interpreted as morning and afternoon periods of different consecutive days. We have a capacity constraint for all tasks that are assigned to the same morning or afternoon of a given day.
- Reformulation
Let denote the index of the last possible interval where the tasks can be assigned: . The constraint can be expressed in term of a set of reified constraints and of arithmetic constraints (i.e.,ย constraints).
For each task and for each interval we create a 0-1 variable that will be set to 1 if and only if the origin of task is assigned within interval :
ย ย ย ย ย ย ย ย
Finally, for each interval , we impose the sum to not exceed the maximum allowed capacity .
- See also
assignment dimension removed: ย (assignment dimension corresponding to intervals is removed).
related: ย ( constraint replaced by ).
- Keywords
-
characteristic of a constraint: automaton, automaton with array of counters.
constraint type: timetabling constraint, resource constraint, temporal constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Sets
-
- Constraint(s) on sets
- Graph model
We use a bipartite graph where each class of vertices corresponds to the different tasks of the collection. There is an arc between two tasks if their origins belong to the same interval. Finally we enforce a constraint on each set of successors of the different vertices of the final graph. This put a restriction on the maximum value of the sum of the attributes of the tasks of .
Partsย (A) andย (B) of Figureย 5.198.2 respectively show the initial and final graph associated with the Example slot. Each connected component of the final graph corresponds to items that are all assigned to the same interval.
Figure 5.198.2. Initial and final graph of the constraint
(a) (b)
- Automaton
Figureย 5.198.3 depicts the automaton associated with the constraint. To each item of the collection corresponds a signature variable that is equal to 1.
Figure 5.198.3. Automaton of the constraint