Resources & Rules¶

Resources constrain paths in graphs. Rules define how resources are updated and checked for feasibility during the dynamic programming pricing.

Resources¶

A resource is defined as a tuple of consumption/bounds data and a name:

resource = ({"E": [...], "V": [...], "G": [...]}, "name")

The dictionary keys specify where data lives:

Key	Type	Description
`"E"`	Edge	Per-edge values. Lists of length `\|E\|`.
`"V"`	Vertex	Per-vertex values. Lists of length `\|V\|`.
`"G"`	Global	Global bounds. Scalars or short lists.

Values can be Python lists or NumPy int32 arrays.

Examples¶

Time window -- edge travel times with per-vertex time windows:

T = [1, 3, 4, 2]   # edge travel times, length |E|
A = [0, 1, 1]       # vertex lower bounds, length |V|
B = [10, 4, 5]      # vertex upper bounds, length |V|
time = {"E": [T], "V": [A, B]}, "time"

Capacity -- vertex consumption with a global upper bound:

D = [2, 2, 3]  # vertex demands, length |V|
q = 10         # vehicle capacity
capacity = {"V": [D], "G": [q]}, "capacity"

Mutually exclusive sets -- vertices assigned to sets via bit IDs:

S = [1, 1, 2]  # set IDs per vertex, length |V|
mes = {"V": [S]}, "mutuallyExclusiveSet"

Adding Resources to Graphs¶

Pass resources when creating a graph:

graph = model.addGraph(edges=E, edgeCosts=C, resources=[time, capacity])

Rules¶

Rules define how resources are updated along a path and how feasibility is checked.

Rule Format¶

rule = ("RuleType", ["resource_name"])
# or with a name
rule = ("RuleType", ["resource_name"], "rule_name")

Rule Types¶

Type	Shorthand	Description
`"Window"`	`"W"`	Time-window style: accumulate + wait. Feasibility checked against per-vertex bounds.
`"Capacity"`	`"C"`	Cumulative: accumulate demand. Feasibility checked against global upper bound.
`"MutuallyExclusiveSets"`	`"MES"`	Bitset-based mutual exclusivity between vertex/edge sets.
`"Bit"`	--	Bit-based resource tracking.
`"BitExclusive"`	--	Exclusive bit rules.
`"BitCount"`	--	Bit counting rules.

You can use the string shorthand or flowty.Rule.Type enum:

capacityRule = "Capacity", ["capacity"]
# equivalent to
capacityRule = flowty.Rule.Type.Capacity, ["capacity"]

Resource Update Functions¶

Window: \(s_j = \max(l_j, s_i + q_{ij})\) -- accumulate and wait for window to open.
Capacity: \(s_j = s_i + q_{ij}\) -- simple accumulation.
MutuallyExclusiveSets: \(s_j = s_i \mid q_{ij}\) -- bitwise OR of visited sets.

Feasibility Checks¶

Window: \(l_v \leq s \leq u_v\) at each vertex.
Capacity: \(s \leq u\) against global bound.
MutuallyExclusiveSets: \((s \oplus u_v) \mathbin{\&} s \leq 0\) -- no conflict with current vertex's set.

Adding Rules to Subproblems¶

timeRule = "Window", ["time"]
loadRule = "Capacity", ["load"]
rules = [timeRule, loadRule]

subproblem = model.addSubproblem(
    graph, source=0, target=n-1, obj=0, lb=1, ub=10, domain="B", rules=rules
)

Implicit Rules¶

When only Window and Capacity rules are needed, they are automatically deduced from the resource data. You can omit the rules parameter:

# Rules are inferred from the resource structure
subproblem = model.addSubproblem(graph, source=0, target=3, obj=0, lb=1, ub=6, domain="I")

Per-Commodity Resources (McfModel)¶

On McfModel, resources can be set globally or per-commodity:

# Global resources
model.setResources(resources)
model.setRules(feasibilityRules, updateRules)

# Per-commodity resources
model.addCommodityWithResources(origin, destination, demand, resources, feasibilityRules, updateRules)

See McfModel for details.

First Resource Ordering¶

The first resource in the list defines the order in which labels are processed in the dynamic programming algorithm. There must not exist a cycle in the graph with zero consumption for the first resource.