[Rule] MinimumEdgeCostFlow to ILP #962
Description
Motivation
Direct ILP formulation for MinimumEdgeCostFlow. Companion issue for #810 (MinimumEdgeCostFlow model). Enables ILP-based solving for fixed-charge network flow instances.
Source
MinimumEdgeCostFlow
Target
ILP (Integer Linear Programming)
Reference
Standard fixed-charge network flow ILP formulation; see Wolsey, Integer Programming.
Reduction Algorithm
Input: A MinimumEdgeCostFlow instance with directed graph G = (V, A), source s, sink t, capacity c(a) and price p(a) for each arc a, and flow requirement R.
- For each arc a ∈ A, create integer variable f_a ∈ {0, 1, ..., c(a)} representing flow.
- For each arc a ∈ A, create binary indicator variable y_a ∈ {0, 1} (y_a = 1 if arc carries nonzero flow).
- Linking constraints: for each arc a, f_a ≤ c(a) · y_a (ensures y_a = 1 when f_a > 0).
- Flow conservation: for each v ∈ V \ {s, t}, Σ_{(u,v)} f_{(u,v)} = Σ_{(v,w)} f_{(v,w)}.
- Flow requirement: Σ_{(u,t)} f_{(u,t)} - Σ_{(t,w)} f_{(t,w)} ≥ R.
- Objective: minimize Σ_{a ∈ A} p(a) · y_a.
Solution extraction: Read the optimal f_a values as the flow assignment.
Size Overhead
| Code metric | Formula |
|---|---|
num_variables |
2 * num_arcs |
num_constraints |
num_arcs + (num_vertices - 2) + 1 |
Where num_arcs = |A|, num_vertices = |V|.
Validation Method
Closed-loop test: construct a MinimumEdgeCostFlow instance, reduce to ILP, solve, extract flow, verify it minimizes edge cost while meeting flow requirement.
Example
Source: 4 vertices, s=0, t=3, R=2. Arcs: (0,1,2,1), (0,2,2,3), (1,3,2,0), (2,3,2,0).
ILP: f_{01}, f_{02}, f_{13}, f_{23} ∈ Z≥0, y_{01}, y_{02}, y_{13}, y_{23} ∈ {0,1}
- f_{01} ≤ 2·y_{01}, f_{02} ≤ 2·y_{02}, f_{13} ≤ 2·y_{13}, f_{23} ≤ 2·y_{23}
- Conservation at 1: f_{01} = f_{13}; at 2: f_{02} = f_{23}
- Flow req: f_{13} + f_{23} ≥ 2
- Minimize: 1·y_{01} + 3·y_{02} + 0·y_{13} + 0·y_{23}
Optimal: f_{01}=2, f_{02}=0, f_{13}=2, f_{23}=0 → y_{01}=1, y_{13}=1 → Min(1).