# 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

\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:

\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

\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

\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
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("MIPGap", 0)

# create subproblems
S = []
for o, d, b in zip(O, D, B):
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
lazy = True
for u, *edges, y in zip(U, *[s.graph.edges for s in S], Y):
model += flowty.sum(edges) <= u * y, lazy

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}")