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

problemreductions/rules/
directedhamiltonianpath_ilp.rs
