Skip to content

Resource Constrained Multi-Commodity Flow Problem

In the RCMCF the objective is to minimize the total cost of transporting commodities through a network from origin to destination vertices. The edges of the network are capacitated. Each edge has a resource consumption (e.g. time) and paths are limited by an upper bound on this consumption per commodity.

Let \(g(V,E)\) be a graph and let \(K\) be the set of commodities each with an origin \(o_k\), destination \(d_k\), and demand \(b_k\). Edge capacity is \(u_e\) for \(e \in E\), resource consumption is \(t_e\) for \(e \in E\), and the limit is \(t_k\) for \(k \in K\).

min⁡∑k∈K∑p∈Pkcpλps.t. ∑p∈Pkλp≥bkk∈K∑k∈K∑p∈Pkαpeλp≤uee∈Eλp≥0k∈K,p∈Pk \begin{aligned} \min{ } & \sum_{k \in K} \sum_{p \in P^k} c_p \lambda_p \\ \text{s.t. } & \sum_{p \in P^k} \lambda_p \geq b_k & & k \in K \\ & \sum_{k \in K} \sum_{p \in P^k} \alpha_p^e \lambda_p \leq u_e & & e \in E \\ & \lambda_p \geq 0 && k \in K, p \in P^k \\ \end{aligned}

where each path \(p \in P^k\) for commodity \(k \in K\) is feasible in \(g(V,E)\) subject to resource constraints.

McfModel requires Path mode for resource constraints

Resource-constrained pricing (Rcspp) is only supported with McfModel.Type.Path, not Tree.

Using McfModel with per-commodity resource constraints and RCSPP pricing:

import flowty

model = flowty.McfModel(flowty.McfModel.Type.Path)
model.setPricing(flowty.McfModel.Pricing.Rcspp)
model.setSlackMode(flowty.McfModel.SlackMode.Edges)
model.setPenalty(1000.0)

# network: 5 vertices, 7 edges
sources    = [0, 0, 1, 1, 2, 3, 3]
targets    = [1, 2, 3, 2, 4, 2, 4]
costs      = [4, 2, 3, 1, 5, 2, 6]
capacities = [5, 8, 4, 3, 6, 3, 5]
model.addEdges(sources, targets, costs, capacities)

# per-edge resource consumption (e.g. transit time)
T = [3, 5, 2, 4, 3, 1, 4]

# commodity 1: limit 8, commodity 2: limit 6
for o, d, b, limit in [(0, 4, 3.0, 8), (1, 4, 2.0, 6)]:
    resources = [({"E": [T], "G": [limit]}, "time")]
    rules = [("Capacity", ["time"], "time_rule")]
    model.addCommodityWithResources(o, d, b, resources, rules, rules)

status = model.solve()
solution = model.getSolution()
if solution:
    print(f"Cost: {solution.cost}")
    print(f"Edge flows: {solution.edgeFlows}")

Using the general Model API with per-commodity graphs and resources:

import flowty

model = flowty.Model()

E = [(0, 1), (0, 2), (1, 3), (1, 2), (2, 4), (3, 2), (3, 4)]
C = [4.0, 2.0, 3.0, 1.0, 5.0, 2.0, 6.0]
U = [5.0, 8.0, 4.0, 3.0, 6.0, 3.0, 5.0]
T = [3, 5, 2, 4, 3, 1, 4]

O = [0, 1]
D = [4, 4]
B = [3.0, 2.0]
R = [8, 6]  # per-commodity resource limits

subproblems = []
for o, d, b, r in zip(O, D, B, R):
    resource = {"E": [T], "G": [r]}, "time"
    rule = "Capacity", ["time"]
    graph = model.addGraph(edges=E, edgeCosts=C, resources=[resource])
    subproblems.append(
        model.addSubproblem(
            graph, source=o, target=d, obj=0, lb=0, ub=b, domain="C",
            rules=[rule]
        )
    )

penalty = sum(C) + 1
Y = [model.addVariable(obj=penalty, lb=0, ub=b, domain="C") for b in B]

for y, s, b in zip(Y, subproblems, B):
    model += y + s >= b

lazy = True
for u, *edges in zip(U, *[s.graph.edges for s in subproblems]):
    model += flowty.sum(edges) <= u, lazy

status = model.solve()
solution = model.getSolution()
if solution:
    print(f"Cost: {solution.cost}")
    for path in solution.paths:
        print(f"Commodity {path.subproblem.id}: {path.x}")
        for edge in path.edges:
            print(f"  {edge}")