# Network Flow Optimization

1. Suppose we have a network with node set $$N = \{1,\dots, n\}$$ and arc set $$E$$. $$(i, j) \in E$$ if there is a link between node $$i$$ and node $$j$$. We need to send $$L$$ commodities from their respective origin to destination node. The multicommodity flow problem has the following specifications:

(a) There are $$L$$ origin-destination (O-D) pairs of nodes $$(s_1, t_1), \dots,(s_L, t_L)$$, and $$d^k$$ is the amount of flow that must be sent from $$s_k$$ to $$t_k$$ for $$k = 1, \dots, L$$.

(b) $$u_{i,j}$$ is the capacity (shared by all commodities) on the arc $$(i, j)$$ for any $$(i, j) \in E$$.

(c) $$c^k_{i,j}$$ is the cost of sending one unit of commodity $$k$$ through arc $$(i, j)$$. Write down an optimization model for the above problem to minimize the total cost.