[Rule] MinimumCapacitatedSpanningTree to ILP

[isPANN]

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.

1. Binary edge variables x_e ∈ {0, 1} for each e ∈ E.
2. Flow variables f_{e,v} ≥ 0 for each edge e and non-root vertex v (multi-commodity flow to model routing).
3. Tree: Σ_e x_e = n - 1, plus subtour elimination via flow.
4. Capacity: for each edge e oriented away from root, Σ_v f_{e,v} · r(v) ≤ c · x_e.
5. 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).

[isPANN]

Please kindly check the following items (PR #976):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.