problemreductions/rules/
hamiltonianpath_ilp.rs

1//! A permutation matrix with direct consecutive-position adjacency constraints.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::HamiltonianPath;
5use crate::reduction;
6use crate::rules::ilp_helpers::{one_hot_assignment_constraints, one_hot_decode};
7use crate::rules::traits::{ReduceTo, ReductionResult};
8use crate::topology::{Graph, SimpleGraph};
9
10/// Binary `x[v,p]` at index `v * n + p` selects vertex v at path position p.
11#[derive(Debug, Clone)]
12pub struct ReductionHamiltonianPathToILP {
13    target: ILP<bool>,
14    num_vertices: usize,
15}
16
17impl ReductionResult for ReductionHamiltonianPathToILP {
18    type Source = HamiltonianPath<SimpleGraph>;
19    type Target = ILP<bool>;
20
21    fn target_problem(&self) -> &ILP<bool> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_witness(
30            self.target_problem(),
31            target_solution,
32            |value| value.value.is_some(),
33            "target ILP assignment is infeasible",
34        )?;
35
36        one_hot_decode(target_solution, self.num_vertices, self.num_vertices, 0)
37    }
38}
39
40#[crate::aggregate_reduction(ilp_feasibility)]
41impl crate::rules::AggregateReductionResult for ReductionHamiltonianPathToILP {}
42
43#[reduction(transform = {
44    exact {
45        max_constraint_magnitude_bits = "1",
46        num_vars = "num_vertices^2",
47        num_constraints = "num_vertices^2 + num_vertices",
48    },
49    upper_bound {
50        num_nonzeros = "3 * num_vertices^2 + 2 * num_vertices * num_edges",
51    },
52})]
53impl ReduceTo<ILP<bool>> for HamiltonianPath<SimpleGraph> {
54    type Result = ReductionHamiltonianPathToILP;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let n = self.num_vertices();
58        let num_vars = n.checked_mul(n).ok_or_else(|| {
59            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(
60                "counting Hamiltonian permutation variables",
61            )
62        })?;
63        <Self as ReduceTo<ILP<bool>>>::exact_i64(n, "bounding adjacency row sums")?;
64        let mut neighbors = vec![Vec::new(); n];
65        for (u, v) in self.graph().edges() {
66            if u != v {
67                neighbors[u].push(v);
68                neighbors[v].push(u);
69            }
70        }
71        let mut constraints = one_hot_assignment_constraints(n, n, 0);
72        for (v, adjacent) in neighbors.iter_mut().enumerate() {
73            adjacent.sort_unstable();
74            adjacent.dedup();
75            for p in 0..n.saturating_sub(1) {
76                let mut terms = vec![(v * n + p, 1)];
77                terms.extend(adjacent.iter().map(|&w| (w * n + p + 1, -1)));
78                constraints.push(LinearConstraint::le(terms, 0));
79            }
80        }
81
82        // Feasibility: no objective
83        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
84            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
85
86        Ok(ReductionHamiltonianPathToILP {
87            target,
88            num_vertices: n,
89        })
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "hamiltonianpath_to_ilp",
97        build: || {
98            // Path graph: 0-1-2-3 (has Hamiltonian path)
99            let source = HamiltonianPath::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
100            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
101        },
102    }]
103}
104
105#[cfg(test)]
106#[path = "../unit_tests/rules/hamiltonianpath_ilp.rs"]
107mod tests;
problemreductions/rules/hamiltonianpath_ilp.rs

problemreductions/rules/
hamiltonianpath_ilp.rs
