Skip to content

Fixed Charge Multi-Commodity Flow Problem

In the FCMCF the objective is to minimize the total cost of routing commodities through a network. In addition to the variable cost per unit on each edge, each edge carries a fixed charge that must be paid for the edge to be used. Also known as the Fixed Charge Network Design Problem.

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\). Let \(G\) be a set containing a copy of \(g\) for each \(k \in K\). Edge capacity is \(u_e\) and fixed cost is \(f_e\) for \(e \in E\).

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}

Strengthened with per-commodity linking: \(\sum_{p \in P^k} \alpha_p^e \lambda_p \leq b_k y_e\) for \(k \in K, e \in E\).

FCMCF requires the Model API

FCMCF needs binary fixed-charge design variables (addVariable) and linking constraints, which McfModel does not support.

import flowty

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

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]
F = [10.0, 8.0, 12.0, 6.0, 9.0, 7.0, 11.0]  # fixed charge per edge

O = [0, 1, 3]
D = [4, 4, 4]
B = [3.0, 2.0, 4.0]

# one graph copy per commodity
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")
    )

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

# fixed-charge design 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: sum of flows <= capacity * design variable
for u, *edges, y in zip(U, *[s.graph.edges for s in S], Y):
    model += flowty.sum(edges) <= u * y

# strong linking: per-commodity flow <= demand * design variable
lazy = True
for b, s in zip(B, S):
    for e, y in zip(s.graph.edges, Y):
        model += e <= b * y, 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:
        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}")