[Rule] SteinerTree to ILP

[zazabap]

Source: SteinerTree
Target: ILP
Motivation: Enables solving Steiner Tree via ILP solvers; the flow-based formulation is the standard in network optimization and VLSI routing tools.
Reference: Wong, 1984; Koch & Martin, 1998

Reduction Algorithm

Notation:

• Source: undirected weighted graph $G = (V, E, w)$, terminals $T \subseteq V$, $n = |V|$, $m = |E|$, $|T| = k$
• Target: ILP with binary and continuous variables

Step 1 — Choose a root: Pick any terminal $r \in T$ as the root. Let $T' = T \setminus {r}$ ($k-1$ non-root terminals).

Step 2 — Variables:

• Edge selection: $y_e \in {0, 1}$ for each edge $e \in E$ (include in tree?)
• Flow: $f^t_{uv} \in [0, 1]$ for each directed arc $(u,v)$ (both directions of each edge) and each non-root terminal $t \in T'$. Represents one unit of flow from $r$ to $t$.

Step 3 — Constraints:

1. Flow conservation (for each $t \in T'$ and each vertex $v \in V$):

$$\sum_{u:(u,v) \in A} f^t_{uv} - \sum_{u:(v,u) \in A} f^t_{vu} = \begin{cases} -1 & \text{if } v = r \ +1 & \text{if } v = t \ 0 & \text{otherwise} \end{cases}$$

2. Capacity linking (for each directed arc $(u,v)$ and each $t \in T'$):

$$f^t_{uv} \leq y_e \quad \text{where } e = {u,v}$$

Objective: minimize $\sum_{e \in E} w_e \cdot y_e$

Solution extraction: Select edges with $y_e = 1$; these form the Steiner tree.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$m + 2m(k-1)$ (edge selection + flow variables)
num_constraints	$n(k-1) + 2m(k-1)$ (conservation + capacity)

Validation Method

Closed-loop testing: solve SteinerTree by brute-force (enumerate edge subsets), solve the reduced ILP, and verify both give the same optimal cost.

Example

Source: 5 vertices, 7 edges, terminals $T = {0, 2, 4}$.

Edge	Weight
$(0,1)$	2
$(1,2)$	2
$(1,3)$	1
$(3,4)$	1
$(0,3)$	5
$(3,2)$	5
$(2,4)$	6

ILP: root $r = 0$, commodities for terminals ${2, 4}$.

• 7 edge variables + 28 flow variables = 35 variables
• 10 conservation + 28 capacity = 38 constraints

Optimal ILP solution: $y = 1$ for edges ${(0,1), (1,2), (1,3), (3,4)}$, objective $= 6$.

Flow for terminal 2: $0 \to 1 \to 2$ (unit flow along path).
Flow for terminal 4: $0 \to 1 \to 3 \to 4$ (unit flow along path).