300. Network Flow

Types of Problems:

• Maximum Flow

• Minimum Cost Flow

• Multi-Commodity Flow

Node

• Sink node: Has demand of units

• Source node: Has supply of units

• Transsipment node: Neither supply or demand

Units shipped from node to node :

Minimize:

s.t.

Where:

• : Unit cost of flow from node to node

• : Demand on node

• : flow lower bound from to

• : Flow upper bound from to

• : Inflow to

• : Outflow from

If:

• Total Supply Total Demand[Inflow to ] - [Outflow from ]

• Total Supply Total Demand[Inflow to ] - [Outflow from ]

• Total Supply Total Demand[Inflow to ] - [Outflow from ]

Important:

• One decision variable for each edge

• One flow balancing constraint for each node

Node Properties:

• Node Type: Source, sink, or intermediary.
• Supply (Source): Flow capacity of source nodes.
• Holding Cost (Intermediary): Inventory cost for stored goods.
• Service Time: Processing time at the node.
• Demand: Required flow at sink nodes.
• Storage Capacity (Intermediary): Maximum amount of goods that can be held at a node
• Penalty for Unfulfilled Demand (Sink): Cost for unmet demand.
• Disruption Risk (All Nodes): Probability of a node being unavailable due to unforeseen circumstances

Edge Properties:

• Edge Type: Transport mode (air, water, road, rail).
• Fixed Cost: Cost incurred for using the edge, regardless of flow.
• Reliability: Probability of edge availability.
• Flow Bounds: Minimum and maximum allowable flow.
• Unit Cost: Cost per unit of flow.
• Lead Time: Time it takes for flow to travel along the edge.
• Environmental Impact: Account for the carbon footprint of using certain transport modes.