Net Mod 3: Minimum Cost Network Flows

Packages Used: No new packages are used in this notebook.

1. Minimum Cost Network Flow

Minimum cost network flow (MCNF) is the most general network model. It can be used to represent a variety of network models that can be solved as an LP. Special procedures more efficient than LP were developed to solve MCNF and Transportation problems, e.g.:

It is usually easier to transform into an LP since current LP solvers are so good, with MCNF just aiding in the formulation of the problem. Special, very efficient procedures are only used for the shortest-path problem (Dijkstra).

Each row i of the arc-incidence matrix and the corresponding net supply represent the coefficients of the flow-balance equation for node i. The LP formulation of the MCNF problem is a follows:

$ \begin{eqnarray*} \quad \mbox{Minimize} \quad \sum_{j \in E} c_j x_j \\ \quad \mbox{subject to} \quad \sum_{j \in E} a_{i,j} x_j &\ge& s_i\mbox{,} &\quad i \in V : s_i < 0 \\ \sum_{j \in E} a_{i,j} x_j &=& s_i\mbox{,} &\quad i \in V : s_i \ge 0 \\ x_j &\ge& 0 \mbox{,} \\ \end{eqnarray*} $

where,

$ \begin{eqnarray*} \quad G(V,E) &=& \mbox{network of nodes } V \mbox{ and arcs } E \ c_j &=& \mbox{arc cost per unit flow} \ xj &=& \mbox{arc flow} \ a{i,j} &=& \begin{cases} -1, & \mbox{node } i \mbox{ is source of arc } j \\ \:\:\, 1, & \mbox{node } i \mbox{ is destination of arc } j \end{cases} \ s_i &=& \mbox{net supply of node } i \ &=& \begin{cases} < 0, & \mbox{supply node } i \ = 0, & \mbox{transshipment node } i \

0, & \mbox{demand node } i \mbox{.} \end{cases} \ \end{eqnarray*} $

Note: Although the net flow $\sum a_{i,j} x_j $ cannot exceed supply $s_i$ for a supply node $i$, the flow-balance constraint is $\sum a_{i,j} x_j \ge s_i $ in the formulation because $a_{i,j} = -1$ and $s_i < 0$.

Ex 1: Transportation Problem as an MCNF Problem

In Ex 4 from Net Mod 1, the LP model was created directly from the interlevel matrix C. Since the transportation problem is a special case of the MCNF problem, C can be converted into an incidence matrix, A, and then solved as an MCNF instance.

image.png

An more concise means of specifying the MCNF model in JuMP is using unnamed constaint containers with conditions, where

for i ∈ V
    if s[i] < 0
        @constraint(model, sum(A[i,j]*x[j] for j ∈ E) >= s[i] )
    else
        @constraint(model, sum(A[i,j]*x[j] for j ∈ E) == s[i] )
    end
end

is replaced with

@constraint(model, [i ∈ V; s[i] < 0], sum(A[i,j]*x[j] for j ∈ E) >= s[i] )
@constraint(model, [i ∈ V; s[i] >= 0], sum(A[i,j]*x[j] for j ∈ E) == s[i] )

Ex 2: MCNF without Arc Bounds

image.png

Arc list information is used to create the incidence matrix for the network that can used as the node-balance constraints in the MCNF LP formulation:

Ex 3: MCNF with Arc Bounds

Upper and lower arc bounds that differ from the default values of $\infty$ and $0$ can easily be added to the MCNF LP formulation.

image.png

Arc (4,5) is the only arc with a lower-bound $>0$, and arcs (2,4), (2,5), and (3,5) are the only arcs with upper-bounds $<\infty$:

Note: In the above arc lists, edge 2 => 5 is defined before edge 2 => 4, but the column for edge 2 => 4 is first in A. As a result, the weight vector w used to define the network g does not correspond to the order that the arcs appear in A and, as a result, the arc cost vector c needs to be explicitly determined by iterating over each edge (e.g., [weights(g)[src(e),dst(e)] for e in edges(g)]). Since this cannot be done for the upper and lower arc bounds, instead, an index array idx is created by iterating over each edge and then used to reorder the arc bounds:

Ex 4: MCNF for Shortest Path

The shortest path problem can be formulated as an MCNF problem by adding a supply/demand of one to starting/terminal nodes and a net supply of $0$ for the other (transshipment) nodes in the network:

image.png

Additional constraints: The only reason to use the MCNF formulation for the shortest path problem would be if there needed to be additional constraints like arc bounds that need to be included in the model of the problem. For example, to find the shortest path in the directed network that always contains the arc from node 2 to node 3, solve as MCNF with LB of arc (2,3) = 1 to force its use:

4. Maximum Flow Models

If all of the arcs in a network have upper bounds $<\infty$, then determining the maximum amount of flow that can occur between source nodes and sink (or demand) nodes can be used to model many different problems.

Ex 5: Single Source/Sink Maximum Flow

In the case that there is a single source and a single sink node, an arc can be added from the sink to the source with a cost of $1$ and an upper bound of $\infty$. All of the other nodes have $0$ net supply and $0$ cost. The resulting flow on the added arc (18) represents the maximum flow in the network.

image.png

image.png

Ex 6: Multiple Source/Sink Maximum Flow Model

In this example of oil pipeline distribution network from Taha, when there are multiple source nodes, an additional node can be added as a new single-source node that is connected to the original source nodes with arcs of $0$ costs and upper bounds of $\infty$; similarly, a new single sink node can be added if there are multiple sink nodes:

image.png

image.png

It can be convienent to enter each arc as a row in a matric when entering network data manually:

4. Production-Inventory Planning Models

Production-inventory planning models are the main use of MP in industry. They provide a means to make complex decisions over a rolling planning horizon. The following production-inventory planning model is for a single product, with a rolling horizon of t periods (e.g., months):

$ \begin{eqnarray*} \quad \mbox{Minimize} \quad \sum_{i=1}^{m} \sum_{j=1}^{t} c_i^p x_{ij} + \sum_{i=1}^{m} \sum_{j=2}^{t+1} c_i^i y_{ij} \\ \quad \mbox{subject to} \quad -x_{ij} + x_{(i+1)j} - y_{ij} + y_{i(j+1)} &=& 0 \mbox{,} &\quad i = 1, \dots, m-1; j = 1, \dots, t &\quad (a) \\ -x_{m,j} - y_{m,j} + y_{m(j+1)} &=& d_j \mbox{,} &\quad j = 1, \dots, t &\quad (b) \\ x_{ij} &\le& u_{ij} \mbox{,} &\quad i = 1, \dots, m; j = 1, \dots, t \\ y_{i,1} &=& y_i^0 \mbox{,} &\quad i = 1, \dots, m \\ y_{i(t+1)} &=& y_i^t \mbox{,} &\quad i = 1, \dots, m \\ x, y &\ge& 0 \mbox{,} \\ \end{eqnarray*} $

where,

$ \begin{eqnarray*} \quad m &=& \mbox{number of production stages} \\ t &=& \mbox{number of periods of production} \\ c_i^p &=& \mbox{production cost (dollar/ton) in stage } i \\ x_{ij} &=& \mbox{production (ton) at stage } i \mbox{ in period } j \\ c_i^i &=& \mbox{inventory cost (dollar/ton) in stage } i \\ y_{ij} &=& \mbox{stage-} i \mbox{ inventory (ton) from period } j-1 \mbox{ to } j \\ d_j &=& \mbox{demand (ton) in period } j \\ u_{ij} &=& \mbox{production capacity (ton) of stage } i \mbox{ in period } j \\ y_i^0 &=& \mbox{initial inventory (ton) of stage } i \\ y_i^t &=& \mbox{final inventory (ton) of stage } i \mbox{.} \\ \end{eqnarray*} $

In the objective function, inventory costs are summed from 2 to t + 1 because the period 1 initial inventory cost was accounted for in period 0 prior to period 1 (rolling horizon). Constraints (a) and (b) in the model are the flow-balance equations for each node, while the remaining constraints represent lower- and upper-bounds on the decision variables x and y.

Ex 7: Three-Month Single-Product Production and Inventory Planning

A single product is produced in two stages. The planning period is three months, and the model is run each month using current demand forecasts and scheduled production capacity. The following shows the production-inventory planning network:

image.png

In the following MCNF formulation, the flow-balance constraints are directly implemented in the model instead of first determining the arc-incidence matrix:

The following shows the optimal production and inventory flows (in blue) in the production-inventory planning network. Note that the flow is balanced at each node; that is, the flow into a node equals the combined production, inventory, and demand flow out of the node.

image.png

Optimal production flows (and required demands):

Optimal inventory flows:

Ex 8: Six-Month Single-Product Production and Inventory Planning

A single product is produced in a two-stage production process. Stage one has a capacity to produce 40 tons of the product per month, and there is a cost of \$200 for each ton of product produced. For stage two, capacity is 80 tons per month, and there is a cost of \\$800 per ton. Due to scheduled maintenance, no capacity will be available during month five for stage 1 and during months three and five for stage 2. Demand for the next six months is estimated to be 25, 15, 10, 50, 25, and 15 tons per month. Currently, five tons of material is in storage at stage 1 and 35 tons at stage 2; at the end of the planning period, ten tons of material should be in storage at stage 1 and 15 at stage 2. Up to 30 tons of material per month can be stored at each stage. Assuming that the inventory costs are \$12 and \\$46 per ton-month, determine the production plan that minimizes total costs over the planning horizon and what the total production costs will be, and what the total inventory costs will be.

Note: The maximum inventory storage constraint can be modeled as an upper bound on y.

Optimal production flows (and required demands):

Optimal inventory flows:

Calculate total production cost and total inventory cost:

Sum of component costs exceeds total cost from solver because it includes first-period (time 0) inventory costs:

Exclude first period from inventory costs:

Total component costs now match total cost from solver: