Skip to content

Multi-Commodity Flow Problem

This example illustrates a model for the Multi-Commodity Flow Problem (MCF).

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 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.

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 capacity is denoted by \(u_e\) for \(e \in E\).

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⁡∑e∈Ecexes.t. xk≥bkk∈Kxe≤uee∈E0≤xk≤bkk∈K \begin{aligned} \min & \sum_{e \in E} c_e x_e \\ \text{s.t. } & x_k \geq b_k & & k \in K \\ & x_e \leq u_e & & e \in E \\ & 0 \leq x_k \leq b_k && k \in K \\ \end{aligned}

with the graph described as above, and domain of each path continuous. The model exploits that the \(|K|\) subproblems for each commodity share a common graph and therefore allows us to model on a single edge in the edge capacity constraint.

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⁡∑e∈Ecexe+∑k∈Kckyks.t. xk+yk≥bkk∈Kxe≤uee∈E0≤xk≤bkk∈K0≤yk≤bkk∈K \begin{aligned} \min & \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 \\ & x_e \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} 

# Multi Commodity Flow
import flowty
import fetch_mcf
import sys

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

# from
# https://commalab.di.unipi.it/datasets/mmcf/#Plnr
# https://github.com/flowty/data/releases/tag/MCF
#
# grid{i}, i in [1,...,15]
# planar{i}, i in [30, 50, 80, 100, 150, 300, 500, 800, 1000, 2500]
instance = "planar500" if len(sys.argv) == 1 else sys.argv[1]
name, n, m, k, E, C, U, O, D, B = fetch_mcf.fetch(instance)

model = flowty.Model()
model.setParam("Pricer_MaxNumCols", k)
model.setParam("Master_MinColInactivity", 2)

# define graph
graph = model.addGraph(edges=E, edgeCosts=C)

# create subproblems
S = [
    model.addSubproblem(graph, source=o, target=d, obj=0, lb=0, ub=b, domain="C")
    for o, d, b in zip(O, D, B)
]

penalty = sum(C) + 1

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

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

# capacity constraints
lazy = True
for e, u in zip(graph.edges, U):
    model += e <= 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}")