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_witness(
38            self.target_problem(),
39            target_solution,
40            |value| value.value.is_some(),
41            "target ILP assignment is infeasible",
42        )?;
43
44        Ok({
45            let n = self.num_vertices;
46            // Decode one-hot assignment: permutation[k] = v where x_{v,k} = 1
47
48            one_hot_decode(target_solution, n, n, 0)?
49        })
50    }
51}
52
53#[crate::aggregate_reduction(ilp_feasibility)]
54impl crate::rules::AggregateReductionResult for ReductionDirectedHamiltonianPathToILP {}
55
56#[reduction(transform = upper_bound {
57    max_constraint_magnitude_bits = "1",
58    num_vars = "num_vertices^2",
59    num_constraints = "3 * num_vertices + num_vertices^3",
60    num_nonzeros = "(num_vertices^2) * (3 * num_vertices + num_vertices^3)",
61})]
62impl ReduceTo<ILP<bool>> for DirectedHamiltonianPath {
63    type Result = ReductionDirectedHamiltonianPathToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let n = self.num_vertices();
67        let arcs = self.graph().arcs();
68
69        // Build arc set for fast lookup
70        let mut arc_set = std::collections::HashSet::new();
71        for (u, v) in &arcs {
72            arc_set.insert((*u, *v));
73        }
74
75        let x_idx = |v: usize, k: usize| -> usize { v * n + k };
76
77        let mut constraints = Vec::new();
78
79        // (1) Assignment: each vertex at exactly one position, each position exactly one vertex
80        // Both row-wise (vertex) and column-wise (position) equality constraints
81        constraints.extend(one_hot_assignment_constraints(n, n, 0));
82        // The helper adds: each item in exactly one slot (row equality), each slot at most one item
83        // But we need each slot exactly one item. Upgrade le to eq for the column constraints:
84        // one_hot_assignment_constraints gives: row eq + col le
85        // We need col eq, so add col ge (col le + col ge = col eq)
86        for k in 0..n {
87            let terms: Vec<(usize, i64)> = (0..n).map(|v| (x_idx(v, k), 1)).collect();
88            constraints.push(LinearConstraint::ge(terms, 1));
89        }
90
91        // (2) Arc existence: for each consecutive position pair (k, k+1),
92        //     forbid (v, w) pairs that are NOT arcs: x_{v,k} + x_{w,k+1} <= 1
93        if n >= 2 {
94            for k in 0..n - 1 {
95                for v in 0..n {
96                    for w in 0..n {
97                        if !arc_set.contains(&(v, w)) {
98                            constraints.push(LinearConstraint::le(
99                                vec![(x_idx(v, k), 1), (x_idx(w, k + 1), 1)],
100                                1,
101                            ));
102                        }
103                    }
104                }
105            }
106        }
107
108        // Feasibility objective
109        let target = ILP::new(n * n, constraints, vec![], ObjectiveSense::Minimize)
110            .map_err(Self::target_construction)?;
111
112        Ok(ReductionDirectedHamiltonianPathToILP {
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: "directedhamiltonianpath_to_ilp",
123        build: || {
124            // Simple directed path: 0->1->2->3
125            let source = DirectedHamiltonianPath::new(crate::topology::DirectedGraph::new(
126                4,
127                vec![(0, 1), (1, 2), (2, 3)],
128            ));
129            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
130        },
131    }]
132}
133
134#[cfg(test)]
135#[path = "../unit_tests/rules/directedhamiltonianpath_ilp.rs"]
136mod tests;
problemreductions/rules/directedhamiltonianpath_ilp.rs

problemreductions/rules/
directedhamiltonianpath_ilp.rs
