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(
39        &self,
40        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
41    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
42        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
43
44        one_hot_decode(target_solution, self.num_vertices, self.num_vertices, 0)
45    }
46}
47
48#[reduction(
49    transform = upper_bound {
50        num_vars = "num_vertices^2 + 2 * num_edges * num_vertices",
51        num_constraints = "2 * num_vertices + 6 * num_edges * num_vertices + num_vertices",
52    },
53    unavailable = {
54        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
55    }
56)]
57impl ReduceTo<ILP<bool>> for HamiltonianPath<SimpleGraph> {
58    type Result = ReductionHamiltonianPathToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let n = self.num_vertices();
62        let graph = self.graph();
63        let edges = graph.edges();
64        let m = edges.len();
65        let n_pos = if n == 0 { 0 } else { n - 1 }; // number of consecutive-position pairs
66
67        let num_x = n * n;
68        let num_z = 2 * m * n_pos;
69        let num_vars = num_x + num_z;
70
71        let x_idx = |v: usize, p: usize| -> usize { v * n + p };
72        let z_fwd_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n_pos + p) };
73        let z_rev_idx = |e: usize, p: usize| -> usize { num_x + 2 * (e * n_pos + p) + 1 };
74
75        let mut constraints = Vec::new();
76
77        // Assignment: one-hot for vertices and positions
78        constraints.extend(one_hot_assignment_constraints(n, n, 0));
79
80        // McCormick linearization for both directions
81        for (e, &(u, v)) in edges.iter().enumerate() {
82            for p in 0..n_pos {
83                // Forward: z_fwd = x_{u,p} * x_{v,p+1}
84                constraints.extend(mccormick_product(
85                    z_fwd_idx(e, p),
86                    x_idx(u, p),
87                    x_idx(v, p + 1),
88                ));
89                // Reverse: z_rev = x_{v,p} * x_{u,p+1}
90                constraints.extend(mccormick_product(
91                    z_rev_idx(e, p),
92                    x_idx(v, p),
93                    x_idx(u, p + 1),
94                ));
95            }
96        }
97
98        // Adjacency: for each consecutive position pair p, exactly one edge
99        for p in 0..n_pos {
100            let mut terms = Vec::new();
101            for e in 0..m {
102                terms.push((z_fwd_idx(e, p), 1));
103                terms.push((z_rev_idx(e, p), 1));
104            }
105            constraints.push(LinearConstraint::eq(terms, 1));
106        }
107
108        // Feasibility: no objective
109        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
110            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
111
112        Ok(ReductionHamiltonianPathToILP {
113            target,
114            num_vertices: n,
115        })
116    }
117}
118
119#[cfg(feature = "example-db")]
120pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
121    vec![crate::example_db::specs::RuleExampleSpec {
122        id: "hamiltonianpath_to_ilp",
123        build: || {
124            // Path graph: 0-1-2-3 (has Hamiltonian path)
125            let source = HamiltonianPath::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
126            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/hamiltonianpath_ilp.rs"]
133mod tests;
problemreductions/rules/hamiltonianpath_ilp.rs

problemreductions/rules/
hamiltonianpath_ilp.rs
