5.159. indexed_sum

Origin

N. Beldiceanu

Constraint

indexed_sum​(ITEMS,​TABLE)​

Argument(s)

ITEMS	collection​(index−dvar,​weight−dvar)​
TABLE	collection​(index−int,​summation−dvar)​

Restriction(s)

|ITEMS|>​0

|TABLE|>​0

required​(ITEMS,​​[index,​weight]​)​

ITEMS.index≥1

ITEMS.index≤|TABLE|

required​(TABLE,​​[index,​summation]​)​

TABLE.index≥1

TABLE.index≤|TABLE|

increasing_seq​(TABLE,​index)​

Purpose

Given several items of the collection ITEMS (each of them having a specific fixed index as well as a weight that may be negative or positive), and a table TABLE (each entry of TABLE corresponding to a summation variable), assign each item to an entry of TABLE so that the sum of the weights of the items assigned to that entry is equal to the corresponding summation variable.

Example

( 〈index−3 weight−−4,​index−1 weight−6,​index−3 weight−1〉,​ 〈index−1 summation−6,​index−2 summation−0,​index−3 summation−−3〉 )

The indexed_sum constraint holds since the summation variables associated with each entry of TABLE are equal to the sum of the weights of the items assigned to the corresponding entry:

• TABLE​[1]​.summation=ITEMS​[2]​.weight=6 (since TABLE​[1]​.index=ITEMS​[2]​.index=1),

• TABLE​[2]​.summation=0 (since TABLE​[2]​.index=2 does not occur as a value of the index attribute of an item of ITEMS),

• TABLE​[3]​.summation=ITEMS​[1]​.weight+ITEMS​[3]​.weight=−4+1=−3 (since TABLE​[3]​.index=ITEMS​[1]​.index=ITEMS​[3]​.index=3).

Reformulation

The indexed_sum​(ITEMS,​TABLE)​ constraint can be expressed in term of a set of reified constraints and of |TABLE| arithmetic constraints (i.e., scalar_product constraints).

1. For each item ITEMS​[i]​ ​(i∈​[1,​|ITEMS|]​)​ and for each table entry j ​(j∈​[1,​|TABLE|]​)​ of TABLE we create a 0-1 variable B_ij that will be set to 1 if and only if ITEMS​[i]​.index is fixed to j (i.e., B_ij⇔ITEMS​[i]​.index=j).

2. For each entry j of the table TABLE, we impose the sum ITEMS​[1]​.weight·B_1j+ITEMS​[2]​.weight·B_2j+...+ITEMS​[|ITEMS|]​.weight·B_|ITEMS|j to be equal to TABLE​[j]​.summation.

See also

bin_packing, bin_packing_capa.

Key words

application area: assignment.

modelling: variable indexing, variable subscript.

For all items of TABLE:

Arc input(s)

ITEMS TABLE

Arc generator

PRODUCT↦collection​(items,​table)​

Arc arity

2

Arc constraint(s)

items.index=table.index

Sets

SUCC↦ [ source,​ variables−col( VARIABLES−collection​(var−dvar)​,​ item​(var−ITEMS.weight)​]​ ) ]

Constraint(s) on sets

sum_ctr​(variables,​=,​TABLE.summation)​

---

Graph model

We enforce the sum_ctr constraint on the weight of the items that are assigned to the same entry. Within the context of the Example slot, part (A) of Figure 5.159.1 shows the initial graphs associated with entries 1, 2 and 3 (i.e., one initial graph for each item of the TABLE collection). Part (B) of Figure 5.159.1 shows the corresponding final graphs associated with entries 1 and 3. Each source vertex of the final graph can be interpreted as an item assigned to a specific entry of TABLE.

Figure 5.159.1. Initial and final graph of the indexed_sum constraint

(a)	(b)