problemreductions/rules/
hamiltonianpath_ilp.rs

1//! Reduction from HamiltonianPath to ILP (Integer Linear Programming).
2//!
3//! Position-assignment formulation:
4//! - Binary x_{v,p}: vertex v at position p
5//! - Binary z_{(u,v),p,dir}: linearized product for edge (u,v) at consecutive positions
6//! - Assignment: each vertex in exactly one position, each position exactly one vertex
7//! - Adjacency: exactly one graph edge between consecutive positions
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::HamiltonianPath;
11use crate::reduction;
12use crate::rules::ilp_helpers::{
13    mccormick_product, one_hot_assignment_constraints, one_hot_decode,
14};
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing HamiltonianPath to ILP.
19///
20/// Variable layout (all binary):
21/// - `x_{v,p}` at index `v * n + p` for `v, p in 0..n`
22/// - `z_{e,p,dir}` at index `n^2 + 2*(e*n_pos + p) + dir` for edge `e`, position `p`,
23///   direction `dir in {0=forward, 1=reverse}`
24#[derive(Debug, Clone)]
25pub struct ReductionHamiltonianPathToILP {
26    target: ILP<bool>,
27    num_vertices: usize,
28}
29
30impl ReductionResult for ReductionHamiltonianPathToILP {
31    type Source = HamiltonianPath<SimpleGraph>;
32    type Target = ILP<bool>;
33
34    fn target_problem(&self) -> &ILP<bool> {
35        &self.target
36    }
37
38    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
39        one_hot_decode(target_solution, self.num_vertices, self.num_vertices, 0)
40    }
41}
42
43#[reduction(
44    overhead = {
45        num_vars = "num_vertices^2 + 2 * num_edges * num_vertices",
46        num_constraints = "2 * num_vertices + 6 * num_edges * num_vertices + num_vertices",
47    }
48)]
49impl ReduceTo<ILP<bool>> for HamiltonianPath<SimpleGraph> {
50    type Result = ReductionHamiltonianPathToILP;
51
52    fn reduce_to(&self) -> Self::Result {
53        let n = self.num_vertices();
54        let graph = self.graph();
55        let edges = graph.edges();
56        let m = edges.len();
57        let n_pos = if n == 0 { 0 } else { n - 1 }; // number of consecutive-position pairs
58
59        let num_x = n * n;
60        let num_z = 2 * m * n_pos;
61        let num_vars = num_x + num_z;
62
63        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
64        let z_fwd_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n_pos + p) };
65        let z_rev_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n_pos + p) + 1 };
66
67        let mut constraints = Vec::new();
68
69        // Assignment: one-hot for vertices and positions
70        constraints.extend(one_hot_assignment_constraints(n, n, 0));
71
72        // McCormick linearization for both directions
73        for (e, &(u, v)) in edges.iter().enumerate() {
74            for p in 0..n_pos {
75                // Forward: z_fwd = x_{u,p} * x_{v,p+1}
76                constraints.extend(mccormick_product(
77                    z_fwd_idx(e, p),
78                    x_idx(u, p),
79                    x_idx(v, p + 1),
80                ));
81                // Reverse: z_rev = x_{v,p} * x_{u,p+1}
82                constraints.extend(mccormick_product(
83                    z_rev_idx(e, p),
84                    x_idx(v, p),
85                    x_idx(u, p + 1),
86                ));
87            }
88        }
89
90        // Adjacency: for each consecutive position pair p, exactly one edge
91        for p in 0..n_pos {
92            let mut terms = Vec::new();
93            for e in 0..m {
94                terms.push((z_fwd_idx(e, p), 1.0));
95                terms.push((z_rev_idx(e, p), 1.0));
96            }
97            constraints.push(LinearConstraint::eq(terms, 1.0));
98        }
99
100        // Feasibility: no objective
101        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
102
103        ReductionHamiltonianPathToILP {
104            target,
105            num_vertices: n,
106        }
107    }
108}
109
110#[cfg(feature = "example-db")]
111pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
112    vec![crate::example_db::specs::RuleExampleSpec {
113        id: "hamiltonianpath_to_ilp",
114        build: || {
115            // Path graph: 0-1-2-3 (has Hamiltonian path)
116            let source = HamiltonianPath::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
117            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/hamiltonianpath_ilp.rs"]
124mod tests;
problemreductions/rules/hamiltonianpath_ilp.rs

problemreductions/rules/
hamiltonianpath_ilp.rs
