Skip to content

Fixed Charge Multi-Commodity Flow Problem

This example illustrates a model for the Fixed Charge Multi-Commodity Flow Problem (FCMCF). The problem is also known as the Fixed Charge Multi-Commodity Network Design Problem.

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 FCMCF the objective is to minimize the total cost of routing commodities through a network over a directed graph from origin to destination vertices. In addition to the variable cost imposed to route each unit of commodity on each edge, each edge of the network has a capacity and carries a fixed charge that must be paid for the edge to be used.

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\) and cost of opening edge \(e \in E\) is \(f_e\).

The problem can be formulated as a path based model

min⁡∑k∈K∑p∈Pkcpλp+∑e∈Efeyes.t. ∑p∈Pkλp≥bkk∈K∑k∈K∑p∈Pkαpeλp≤ueyee∈Eλp≥0k∈K,p∈Pkye∈{0,1}e∈E \begin{aligned} \min{ } & \sum_{k \in K} \sum_{p \in P^k} c_p \lambda_p + \sum_{e \in E} f_e y_e \\ \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 y_e & & e \in E \\ & \lambda_p \geq 0 && k \in K, p \in P^k \\ & y_e \in \{0,1\} && e \in E \\ \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 model can be strengthened by adding:

∑p∈Pkαpeλp≤bkyek∈K,e∈E \begin{aligned} & \sum_{p \in P^k} \alpha_p^e \lambda_p \leq b_k y_e & & k \in K, e \in E \\ \end{aligned}

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

The problem including the strengthening can in Flowty be modeled as

min⁡∑g∈G∑e∈Ecexeg+∑e∈Efeyes.t. xk≥bkk∈K∑g∈Gxeg≤ueyee∈Exeg≤bkyek∈K,e∈E,g∈G0≤xk≤bkk∈Kye∈{0,1}e∈E \begin{aligned} \min & \sum_{g \in G} \sum_{e \in E} c_e x^g_e + \sum_{e \in E} f_e y_e \\ \text{s.t. } & x_k \geq b_k & & k \in K \\ & \sum_{g \in G} x^g_e \leq u_e y_e & & e \in E \\ & x^g_e \leq b_k y_e & & k \in K, e \in E, g \in G \\ & 0 \leq x_k \leq b_k && k \in K \\ & y_e \in \{0,1\} && e \in E \\ \end{aligned}

with the graph described as above, domain of each path continuous, and domain of fixed-charge variables binary. 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+∑e∈Efeye+∑k∈Kckzks.t. xk+zk≥bkk∈K∑g∈Gxeg≤ueyee∈Exeg≤bkyek∈K,e∈E,g∈G0≤xk≤bkk∈K0≤zk≤bkk∈Kye∈{0,1}e∈E \begin{aligned} \min & \sum_{g \in G} \sum_{e \in E} c_e x^g_e + \sum_{e \in E} f_e y_e + \sum_{k \in K} c_k z_k \\ \text{s.t. } & x_k + z_k \geq b_k & & k \in K \\ & \sum_{g \in G} x^g_e \leq u_e y_e & & e \in E \\ & x^g_e \leq b_k y_e & & k \in K, e \in E, g \in G \\ & 0 \leq x_k \leq b_k && k \in K \\ & 0 \leq z_k \leq b_k && k \in K \\ & y_e \in \{0,1\} && e \in E \\ \end{aligned} 

# Fixed Charge Multi Commodity Flow
import flowty
import fetch_fcmcf
import sys

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

# From
# http://groups.di.unipi.it/optimize/Data/MMCF.html#Canad
# https://github.com/flowty/data/releases/tag/FCMCF
instance = "c33" if len(sys.argv) == 1 else sys.argv[1]
name, n, m, k, E, C, U, F, O, D, B = fetch_fcmcf.fetch(instance)

model = flowty.Model()
model.setParam("Pricer_MaxNumCols", k)
model.setParam("MIPGap", 0)

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

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

# fixed-charge variables
Y = [model.addVariable(obj=f, lb=0, ub=1, domain="B") for f in F]

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

# capacity constraints
for u, *edges, y in zip(U, *[s.graph.edges for s in S], Y):
    model += flowty.sum(edges) <= u * y

# strong linking
lazy = True
for b, s in zip(B, S):
    for e, y in zip(s.graph.edges, Y):
        model += e <= b * y, 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)}")
    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:
        if var.variable.id < len(Z):
            print(f"Penalty {var.variable.id}: {var.x}")
        else:
            print(f"Design {var.variable.id - len(Z)}: {var.x}")