[Rule] OptimumCommunicationSpanningTree to ILP

[isPANN]

Motivation

Direct ILP formulation for OptimumCommunicationSpanningTree. Companion issue for #906.

Source

OptimumCommunicationSpanningTree

Target

ILP

Reference

Standard multi-commodity flow ILP for minimum routing cost spanning tree.

Reduction Algorithm

Input: Complete graph K_n with weights w(e) and requirements r({u,v}).

1. Binary edge variables x_e ∈ {0, 1} for each edge.
2. Tree: Σ_e x_e = n - 1, subtour elimination constraints.
3. Path variables: for each pair (u,v), flow variables to compute W_T({u,v}).
4. Objective: minimize Σ_{u,v} W_T({u,v}) · r({u,v}).

Size Overhead

Code metric	Formula
num_variables	O(n^4)
num_constraints	O(n^4)

Validation Method

Closed-loop test.

Example

Source: K3, w(0,1)=1, w(0,2)=2, w(1,2)=3. r(0,1)=1, r(0,2)=1, r(1,2)=1.
Optimal: Tree {(0,1),(0,2)}, cost = 1·1 + 2·1 + 3·1 = 6. Min(6).

[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.