problemreductions/rules/
hamiltoniancircuit_quadraticassignment.rs

1//! Reduction from HamiltonianCircuit to QuadraticAssignment.
2//!
3//! Uses the Sahni & Gonzalez (1976) construction. The cost matrix encodes
4//! cycle adjacency on positions: c[i][j] = 1 if j = (i+1) mod n, else 0.
5//! The distance matrix encodes graph connectivity: d[k][l] = 1 if {k,l} ∈ E,
6//! else ω = n+1 (penalty). A Hamiltonian circuit exists iff the QAP optimum
7//! equals n.
8
9use crate::models::algebraic::QuadraticAssignment;
10use crate::models::graph::HamiltonianCircuit;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing HamiltonianCircuit to QuadraticAssignment.
16#[derive(Debug, Clone)]
17pub struct ReductionHamiltonianCircuitToQuadraticAssignment {
18    target: QuadraticAssignment,
19}
20
21impl ReductionResult for ReductionHamiltonianCircuitToQuadraticAssignment {
22    type Source = HamiltonianCircuit<SimpleGraph>;
23    type Target = QuadraticAssignment;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        // QAP config is a permutation γ mapping positions to vertices,
31        // which is directly the Hamiltonian circuit visit order.
32        target_solution.to_vec()
33    }
34}
35
36#[reduction(
37    overhead = {
38        num_facilities = "num_vertices",
39        num_locations = "num_vertices",
40    }
41)]
42impl ReduceTo<QuadraticAssignment> for HamiltonianCircuit<SimpleGraph> {
43    type Result = ReductionHamiltonianCircuitToQuadraticAssignment;
44
45    fn reduce_to(&self) -> Self::Result {
46        let n = self.num_vertices();
47        let omega = (n + 1) as i64;
48
49        // Cost matrix C: cycle adjacency on positions.
50        // c[i][j] = 1 if j == (i+1) mod n, else 0.
51        let cost_matrix: Vec<Vec<i64>> = (0..n)
52            .map(|i| {
53                (0..n)
54                    .map(|j| if j == (i + 1) % n { 1 } else { 0 })
55                    .collect()
56            })
57            .collect();
58
59        // Distance matrix D: graph connectivity.
60        // d[k][l] = 1 if {k,l} ∈ E, else ω (penalty) for k ≠ l; d[k][k] = 0.
61        let distance_matrix: Vec<Vec<i64>> = (0..n)
62            .map(|k| {
63                (0..n)
64                    .map(|l| {
65                        if k == l {
66                            0
67                        } else if self.graph().has_edge(k, l) {
68                            1
69                        } else {
70                            omega
71                        }
72                    })
73                    .collect()
74            })
75            .collect();
76
77        let target = QuadraticAssignment::new(cost_matrix, distance_matrix);
78        ReductionHamiltonianCircuitToQuadraticAssignment { target }
79    }
80}
81
82#[cfg(feature = "example-db")]
83pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
84    use crate::export::SolutionPair;
85
86    vec![crate::example_db::specs::RuleExampleSpec {
87        id: "hamiltoniancircuit_to_quadraticassignment",
88        build: || {
89            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
90            crate::example_db::specs::rule_example_with_witness::<_, QuadraticAssignment>(
91                source,
92                SolutionPair {
93                    source_config: vec![0, 1, 2, 3],
94                    target_config: vec![0, 1, 2, 3],
95                },
96            )
97        },
98    }]
99}
100
101#[cfg(test)]
102#[path = "../unit_tests/rules/hamiltoniancircuit_quadraticassignment.rs"]
103mod tests;
problemreductions/rules/hamiltoniancircuit_quadraticassignment.rs

problemreductions/rules/
hamiltoniancircuit_quadraticassignment.rs
