Skip to content

Packing Sets

Packing sets are sets BB of variables where

iBxi1\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])


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 BB-elementary paths. That is, paths that only uses one edge (variable) in the packing set BB.


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