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 minimum cost MCF he 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 edge each is associated a transit time and paths are limited by a total transit time.

Let \(g(V,E)\) be a graph and let \(K\) be the set of commodities each with an origin \(o_k\) and destination \(d_k\) and a demand \(b_k\). Edge capacities is denoted by \(u_e\) for \(e \in E\). Transit times are given as \(t_e\) for \(e \in E\) and the transit time is specified for each commodity as \(t_k\).

The problem can be formulated as a path based model

minkKpPkcpλps.t. pPkλpbkkKkKpPkαpeλpueeEλp0kK,pPk \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 \geq 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 = \sum_{e \in p} 1\) expresses \(p\)'s usage of edge \(e\).

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

The problem can in Flowty be modeled as

mingGeEcexe+kKckyks.t. xk+ykbkkK(V,E)G:eExeguee(V,E)GE0xkbkkK \begin{aligned} \min & \sum_{g \in G} \sum_{e \in E} c_e x_e + \sum_{k \in K} c_ky_k \\ \text{s.t. } & x_k + y_k \geq b_k & & k \in K \\ & \sum_{(V,E) \in G: e \in E} x_e^g \leq u_e & & e \in \cup_{(V,E) \in G}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.

See the concepts section and modelling tour for more details.

Fetching data

To fetch the benchmark data check out the examples.

# Resource Constrained Multi Commodity Flow
import flowty
import fetch_rcmcf

name, n, m, k, E, C, U, O, D, B, R, T = fetch_rcmcf.fetch("Med_base_best")

model = flowty.Model()

# create subproblems
subproblems = []
for o, d, b, r in zip(O, D, B, R):
    graph = model.addGraph(costs=C, edges=E, 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

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}")
    for var in solution.variables:
        print(f"Penalty {var.variable.id}: {var.x}")