Skip to content

Resource Constrained Multi-Commodity Flow Problem

This example illustrates a model for the Resource Constrained Multi-Commodity Flow Problem (RCMCF).

In the following, notation \(c_*\) refers to the cost of entity \(*\), and similarly \(x_*\) refers to the variable, e.g., \(c_e\) is the cost of edge \(e\). Entity should be clear from context.

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. To each edge is associated a resource consumption, e.g., time, and paths are limited by an upper bound on this consumption.

Let \(g(V,E)\) be a graph and let \(K\) be the set of commodities each with an origin \(o_k \in E\), destination \(d_k \in E\), and demand \(b_k\) for \(k \in K\). Let \(G\) be a set containing af copy of \(g\) for each \(k \in K\). Edge capacities is denoted by \(u_e\) for \(e \in E\), resource consumption is given as \(t_e\) for \(e \in E\), and the limit is specified as \(t_k\) for \(k \in K\).

The problem can be formulated as a path based model

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)\) with accumulated edge cost \(c_p = \sum_{e \in p} c_e\) and \(\alpha_p^e = |e \cap p|\) expresses \(p\)'s usage of edge \(e\).

The \(\lambda\)'s are not directly available for modelling.

The problem can in Flowty be modeled as

min⁡∑g∈G∑e∈Ecexegs.t. xk≥bkk∈K∑g∈Gxeg≤uee∈E0≤xk≤bkk∈K \begin{aligned} \min & \sum_{g \in G} \sum_{e \in E} c_e x^g_e \\ \text{s.t. } & x_k \geq b_k & & k \in K \\ & \sum_{g \in G} x_e^g \leq u_e & & e \in E \\ & 0 \leq x_k \leq b_k && k \in K \\ \end{aligned}

with the graph and resource constraint described as above, and domain of each path continuous. Variable \(x^g_e\) represents use of edge \(e\) in graph \(g \in G\).

See the concepts section and modelling tour for more details.

Fetching data

To fetch the benchmark data check out the examples.

Adding a penalty term \(c_k\) for \(k \in K\) for not covering a commodity ensures that the model is always feasible

min⁡∑g∈G∑e∈Ecexeg+∑k∈Kckyks.t. xk+yk≥bkk∈K∑g∈Gxeg≤uee∈E0≤xk≤bkk∈K0≤yk≤bkk∈K \begin{aligned} \min & \sum_{g \in G} \sum_{e \in E} c_e x^g_e + \sum_{k \in K} c_ky_k \\ \text{s.t. } & x_k + y_k \geq b_k & & k \in K \\ & \sum_{g \in G} x_e^g \leq u_e & & e \in E \\ & 0 \leq x_k \leq b_k && k \in K \\ & 0 \leq y_k \leq b_k && k \in K \\ \end{aligned} 

# Resource Constrained Multi Commodity Flow
import flowty
import fetch_rcmcf
import sys

if len(sys.argv) == 2 and sys.argv[1] == "--help":
    print("Usage: python rcmcf.py instanceName [logFilepath] [timeLimit]")
    sys.exit(1)

# from
# https://github.com/flowty/LINERLIB
# https://github.com/flowty/flow-first-route-next-heuristic-shipping-network-design
# https://github.com/flowty/data/releases/download/RCMCF
instance = "WorldLarge-All-5" if len(sys.argv) == 1 else sys.argv[1]
name, n, m, k, E, C, U, O, D, B, R, T = fetch_rcmcf.fetch(instance)

model = flowty.Model()
model.setParam("Pricer_MultiThreading", False)
model.setParam("Pricer_MaxNumCols", k * 1000)
model.setParam("Pricer_UseSparseStorage", True)
model.setParam("Pricer_Algorithm", 2)
model.setParam("pricer_HeuristicLowFilter", 0)
model.setParam("pricer_HeuristicHighFilter", 0)

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

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

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

# capacity constraints
lazy = True
maxCapacity = sum(B) + 1
for u, *edges in zip(U, *[s.graph.edges for s in subproblems]):
    if u < maxCapacity:
        model += flowty.sum(edges) <= u, lazy

if len(sys.argv) > 2:
    model.setParam("LogFilepath", sys.argv[2])
if len(sys.argv) > 3:
    model.setParam("TimeLimit", int(sys.argv[3]))

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