Reduction Algorithm
Notation:
- Source: graph G=(V,E) with n=|V| vertices, m=|E| edges, edge weights w: E → R
- Target: ILP with binary variables, linear constraints, and linear objective
Variable mapping:
- For each vertex v ∈ V and position k ∈ {0,...,n-1}, introduce a binary variable x_{v,k}
meaning "vertex v is at position k in the tour"
- Total: n² variables
Constraints:
- Each vertex has exactly one position: Σ_k x_{v,k} = 1 for all v ∈ V
- Each position has exactly one vertex: Σ_v x_{v,k} = 1 for all k
- Non-edges cannot be consecutive: if (v,w) ∉ E, then x_{v,k} + x_{w,(k+1) mod n} ≤ 1 for all k
Objective: Minimize Σ_{(v,w)∈E} w(v,w) · Σ_k x_{v,k} · x_{w,(k+1) mod n}
Note: the products x_{v,k} · x_{w,(k+1) mod n} are quadratic and need linearization.
Introduce auxiliary y_{v,w,k} = x_{v,k} · x_{w,(k+1) mod n} with standard McCormick constraints:
- y_{v,w,k} ≤ x_{v,k}
- y_{v,w,k} ≤ x_{w,(k+1) mod n}
- y_{v,w,k} ≥ x_{v,k} + x_{w,(k+1) mod n} - 1
Solution extraction follows from the variable mapping: read x_{v,k}, for each position k
find the vertex v with x_{v,k} = 1, then output the corresponding edge selection.
Size Overhead
| Target metric |
Polynomial (using symbols above) |
| num_vars |
n² + n²·m |
| num_constraints |
2n + n·(n²−m) + 3·n²·m |
Validation Method
- Closed-loop: reduce → solve ILP → extract tour → verify it visits all vertices and has optimal cost
- Cross-check with brute force: for small graphs (n ≤ 8), enumerate all n!/2n tours and compare costs
- External reference: Python
networkx + itertools.permutations for ground truth
- Negative cases: graphs with no Hamiltonian cycle should yield infeasible ILP
Example Source Instance
Use the test instances from the src problem, i.e., HamiltonianCycle problem.
Reduction Algorithm
Notation:
Variable mapping:
meaning "vertex v is at position k in the tour"
Constraints:
Objective: Minimize Σ_{(v,w)∈E} w(v,w) · Σ_k x_{v,k} · x_{w,(k+1) mod n}
Note: the products x_{v,k} · x_{w,(k+1) mod n} are quadratic and need linearization.
Introduce auxiliary y_{v,w,k} = x_{v,k} · x_{w,(k+1) mod n} with standard McCormick constraints:
Solution extraction follows from the variable mapping: read x_{v,k}, for each position k
find the vertex v with x_{v,k} = 1, then output the corresponding edge selection.
Size Overhead
Validation Method
networkx+itertools.permutationsfor ground truthExample Source Instance
Use the test instances from the src problem, i.e., HamiltonianCycle problem.