problemreductions/rules/
directedhamiltonianpath_ilp.rs

1//! Reduction from DirectedHamiltonianPath to ILP (Integer Linear Programming).
2//!
3//! Position-assignment formulation:
4//! - Binary x_{v,k}: vertex v at position k, total n^2 variables
5//! - Assignment: each vertex in exactly one position, each position exactly one vertex
6//! - Arc existence: for each consecutive position pair (k, k+1), any pair (v, w) where
7//!   (v, w) is NOT a directed arc is forbidden: x_{v,k} + x_{w,k+1} <= 1
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::DirectedHamiltonianPath;
11use crate::reduction;
12use crate::rules::ilp_helpers::{one_hot_assignment_constraints, one_hot_decode};
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing DirectedHamiltonianPath to ILP.
16///
17/// Variable layout (all binary):
18/// - `x_{v,k}` at index `v * n + k` for `v, k in 0..n`
19#[derive(Debug, Clone)]
20pub struct ReductionDirectedHamiltonianPathToILP {
21    target: ILP<bool>,
22    num_vertices: usize,
23}
24
25impl ReductionResult for ReductionDirectedHamiltonianPathToILP {
26    type Source = DirectedHamiltonianPath;
27    type Target = ILP<bool>;
28
29    fn target_problem(&self) -> &ILP<bool> {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok({
40            let n = self.num_vertices;
41            // Decode one-hot assignment: permutation[k] = v where x_{v,k} = 1
42
43            one_hot_decode(target_solution, n, n, 0)?
44        })
45    }
46}
47
48#[reduction(
49    transform = exact {
50        num_vars = "num_vertices^2",
51        num_constraints = "3 * num_vertices + (num_vertices - 1) * (num_vertices^2 - num_arcs)",
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 DirectedHamiltonianPath {
58    type Result = ReductionDirectedHamiltonianPathToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let n = self.num_vertices();
62        let arcs = self.graph().arcs();
63
64        // Build arc set for fast lookup
65        let mut arc_set = std::collections::HashSet::new();
66        for (u, v) in &arcs {
67            arc_set.insert((*u, *v));
68        }
69
70        let x_idx = |v: usize, k: usize| -> usize { v * n + k };
71
72        let mut constraints = Vec::new();
73
74        // (1) Assignment: each vertex at exactly one position, each position exactly one vertex
75        // Both row-wise (vertex) and column-wise (position) equality constraints
76        constraints.extend(one_hot_assignment_constraints(n, n, 0));
77        // The helper adds: each item in exactly one slot (row equality), each slot at most one item
78        // But we need each slot exactly one item. Upgrade le to eq for the column constraints:
79        // one_hot_assignment_constraints gives: row eq + col le
80        // We need col eq, so add col ge (col le + col ge = col eq)
81        for k in 0..n {
82            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, k), 1)).collect();
83            constraints.push(LinearConstraint::ge(terms, 1));
84        }
85
86        // (2) Arc existence: for each consecutive position pair (k, k+1),
87        //     forbid (v, w) pairs that are NOT arcs: x_{v,k} + x_{w,k+1} <= 1
88        if n >= 2 {
89            for k in 0..n - 1 {
90                for v in 0..n {
91                    for w in 0..n {
92                        if !arc_set.contains(&(v, w)) {
93                            constraints.push(LinearConstraint::le(
94                                vec![(x_idx(v, k), 1), (x_idx(w, k + 1), 1)],
95                                1,
96                            ));
97                        }
98                    }
99                }
100            }
101        }
102
103        // Feasibility objective
104        let target = ILP::new(n * n, constraints, vec![], ObjectiveSense::Minimize)
105            .map_err(Self::target_construction)?;
106
107        Ok(ReductionDirectedHamiltonianPathToILP {
108            target,
109            num_vertices: n,
110        })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    vec![crate::example_db::specs::RuleExampleSpec {
117        id: "directedhamiltonianpath_to_ilp",
118        build: || {
119            // Simple directed path: 0->1->2->3
120            let source = DirectedHamiltonianPath::new(crate::topology::DirectedGraph::new(
121                4,
122                vec![(0, 1), (1, 2), (2, 3)],
123            ));
124            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
125        },
126    }]
127}
128
129#[cfg(test)]
130#[path = "../unit_tests/rules/directedhamiltonianpath_ilp.rs"]
131mod tests;
problemreductions/rules/directedhamiltonianpath_ilp.rs

problemreductions/rules/
directedhamiltonianpath_ilp.rs
