problemreductions/rules/
hamiltoniancircuit_quadraticassignment.rs

1//! Reduction from HamiltonianCircuit to QuadraticAssignment.
2//!
3//! Uses an exact-decision normalization of the Sahni & Gonzalez (1976)
4//! cycle-position construction. The QAP cost counts missing edges in a cyclic
5//! permutation, so zero cost certifies a Hamiltonian circuit. Sources with fewer
6//! than three vertices map to a fixed positive-cost instance.
7
8use crate::models::algebraic::QuadraticAssignment;
9use crate::models::decision::Decision;
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: Decision<QuadraticAssignment>,
19}
20
21impl ReductionResult for ReductionHamiltonianCircuitToQuadraticAssignment {
22    type Source = HamiltonianCircuit<SimpleGraph>;
23    type Target = Decision<QuadraticAssignment>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target assignment does not certify a Hamiltonian circuit",
38        )?;
39
40        // Zero cost makes this permutation itself a Hamiltonian circuit.
41        Ok(target_solution.to_vec())
42    }
43}
44
45#[crate::aggregate_reduction(identity)]
46impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToQuadraticAssignment {}
47
48#[reduction(
49    transform = upper_bound {
50        num_facilities = "num_vertices + 3",
51        num_locations = "num_vertices + 3",
52    }
53)]
54impl ReduceTo<Decision<QuadraticAssignment>> for HamiltonianCircuit<SimpleGraph> {
55    type Result = ReductionHamiltonianCircuitToQuadraticAssignment;
56
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let source_n = self.num_vertices();
59        // The source requires at least three vertices. For smaller graphs use
60        // three positions with every distinct pair charged, hence optimum 3.
61        let n = source_n.max(3);
62        let cost_matrix: Vec<Vec<i64>> = (0..n)
63            .map(|i| (0..n).map(|j| i64::from(j == (i + 1) % n)).collect())
64            .collect();
65        let distance_matrix: Vec<Vec<i64>> = (0..n)
66            .map(|k| {
67                (0..n)
68                    .map(|l| i64::from(k != l && (source_n < 3 || !self.graph().has_edge(k, l))))
69                    .collect()
70            })
71            .collect();
72
73        let target = QuadraticAssignment::new(cost_matrix, distance_matrix);
74        Ok(ReductionHamiltonianCircuitToQuadraticAssignment {
75            target: Decision::new(target, 0),
76        })
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![crate::example_db::specs::RuleExampleSpec {
85        id: "hamiltoniancircuit_to_quadraticassignment",
86        build: || {
87            let source = HamiltonianCircuit::new(SimpleGraph::cycle(4));
88            crate::example_db::specs::rule_example_with_witness::<_, Decision<QuadraticAssignment>>(
89                source,
90                SolutionPair {
91                    source_config: serde_json::json!(vec![0, 1, 2, 3]),
92                    target_config: serde_json::json!(vec![0, 1, 2, 3]),
93                },
94            )
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/hamiltoniancircuit_quadraticassignment.rs"]
101mod tests;
problemreductions/rules/hamiltoniancircuit_quadraticassignment.rs

problemreductions/rules/
hamiltoniancircuit_quadraticassignment.rs
