Packing Sets¶

Packing sets are sets $B$ of variables where

$\sum_{i \in B} x_i \leq 1$

Packing sets may include variables from multiple graphs as well as non-graph variables. Add packing sets using the addPackingSet() function like

# packing set x1 + x2 <= 1
m.addPackingSet([x1, x2])

Modeling

Packing Sets are not derived from the model but must be specified by the user.

Packing Set Elementary Paths¶

The dynamic-programming algorithm exploits packing sets to construct $B$ -elementary paths. That is, paths that only uses one edge (variable) in the packing set $B$ .

Branching¶

Packing sets are used to derive branching decisions that may be more efficient than branching on edges explicitly.