Motivation
Direct ILP formulation for MinimumCapacitatedSpanningTree. Companion issue for #901.
Source
MinimumCapacitatedSpanningTree
Target
ILP
Reference
Gavish (1983), "Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem."
Reduction Algorithm
Input: Graph G = (V, E), weights w, root v₀, requirements r, capacity c.
- Binary edge variables x_e ∈ {0, 1} for each e ∈ E.
- Flow variables f_{e,v} ≥ 0 for each edge e and non-root vertex v (multi-commodity flow to model routing).
- Tree: Σ_e x_e = n - 1, plus subtour elimination via flow.
- Capacity: for each edge e oriented away from root, Σ_v f_{e,v} · r(v) ≤ c · x_e.
- Objective: minimize Σ_e w(e) · x_e.
Size Overhead
| Code metric |
Formula |
num_variables |
num_edges + num_edges * (num_vertices - 1) |
num_constraints |
O(num_edges * num_vertices) |
Validation Method
Closed-loop test.
Example
Source: 3 vertices, root=0, edges (0,1,w=1), (0,2,w=2), (1,2,w=1), reqs r(1)=1, r(2)=1, c=1.
Optimal: Tree {(0,1),(0,2)}, weight=3. Min(3).
Motivation
Direct ILP formulation for MinimumCapacitatedSpanningTree. Companion issue for #901.
Source
MinimumCapacitatedSpanningTreeTarget
ILPReference
Gavish (1983), "Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem."
Reduction Algorithm
Input: Graph G = (V, E), weights w, root v₀, requirements r, capacity c.
Size Overhead
num_variablesnum_constraintsValidation Method
Closed-loop test.
Example
Source: 3 vertices, root=0, edges (0,1,w=1), (0,2,w=2), (1,2,w=1), reqs r(1)=1, r(2)=1, c=1.
Optimal: Tree {(0,1),(0,2)}, weight=3. Min(3).