problemreductions/rules/
hamiltoniancircuit_ilp.rs

1//! Degree two and a single bounded flow enforce a spanning cycle.
2
3use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::HamiltonianCircuit;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6use crate::topology::{Graph, SimpleGraph};
7
8type Target = ILP<i64, i64, Bounded>;
9
10#[derive(Debug, Clone)]
11pub struct ReductionHamiltonianCircuitToILP {
12    target: Target,
13    graph: SimpleGraph,
14}
15
16impl ReductionResult for ReductionHamiltonianCircuitToILP {
17    type Source = HamiltonianCircuit<SimpleGraph>;
18    type Target = Target;
19
20    fn target_problem(&self) -> &Target {
21        &self.target
22    }
23
24    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
25        crate::rules::traits::validate_target_witness(
26            self.target_problem(),
27            solution,
28            |value| value.value.is_some(),
29            "target ILP assignment is infeasible",
30        )?;
31        let selected: Vec<_> = solution[..self.graph.num_edges()]
32            .iter()
33            .map(|&value| value == 1)
34            .collect();
35        crate::rules::graph_helpers::edges_to_cycle_order(&self.graph, &selected)
36    }
37}
38
39#[crate::aggregate_reduction(ilp_feasibility)]
40impl crate::rules::AggregateReductionResult for ReductionHamiltonianCircuitToILP {}
41
42#[crate::reduction(transform = upper_bound {
43    num_vars = "3 * num_edges",
44    num_constraints = "2 * num_vertices + 2 * num_edges + 1",
45    num_nonzeros = "10 * num_edges",
46    max_constraint_magnitude_bits = "num_vertices + 2",
47})]
48impl ReduceTo<ILP<i64, i64, Bounded>> for HamiltonianCircuit<SimpleGraph> {
49    type Result = ReductionHamiltonianCircuitToILP;
50    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
51        let n = self.num_vertices();
52        let mut edges: Vec<_> = self
53            .graph()
54            .edges()
55            .into_iter()
56            .filter(|(u, v)| u != v)
57            .map(|(u, v)| (u.min(v), u.max(v)))
58            .collect();
59        edges.sort_unstable();
60        edges.dedup();
61        let m = edges.len();
62        let count =
63            m.checked_mul(3).ok_or(
64                crate::rules::ReductionError::integer_overflow::<Self, Target>(
65                    "counting circuit flow variables",
66                ),
67            )?;
68        let capacity = <Self as ReduceTo<Target>>::exact_i64(
69            n.saturating_sub(1),
70            "bounding spanning-cycle flow",
71        )?;
72        let mut variables = vec![IntegerVariable::binary(); m];
73        variables.resize(
74            count,
75            IntegerVariable::new(Some(0), Some(capacity))
76                .map_err(<Self as ReduceTo<Target>>::target_construction)?,
77        );
78        let mut degree = vec![Vec::new(); n];
79        let mut balance = vec![Vec::new(); n];
80        let mut constraints = Vec::new();
81        for (edge, &(u, v)) in edges.iter().enumerate() {
82            degree[u].push((edge, 1));
83            degree[v].push((edge, 1));
84            for (direction, (from, to)) in [(u, v), (v, u)].into_iter().enumerate() {
85                let flow = m + 2 * edge + direction;
86                balance[from].push((flow, 1));
87                balance[to].push((flow, -1));
88                constraints.push(LinearConstraint::le(vec![(flow, 1), (edge, -capacity)], 0));
89            }
90        }
91        for (v, (degree, balance)) in degree.into_iter().zip(balance).enumerate() {
92            constraints.push(LinearConstraint::eq(degree, 2));
93            constraints.push(LinearConstraint::eq(
94                balance,
95                if v == 0 { capacity } else { -1 },
96            ));
97        }
98        if n < 3 {
99            constraints.push(LinearConstraint::eq(vec![], 1));
100        }
101        let target =
102            Target::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
103                .map_err(<Self as ReduceTo<Target>>::target_construction)?;
104        Ok(ReductionHamiltonianCircuitToILP {
105            target,
106            graph: SimpleGraph::new(n, edges),
107        })
108    }
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "hamiltoniancircuit_to_ilp",
115        build: || {
116            crate::example_db::specs::rule_example_via_bounded_ilp(HamiltonianCircuit::new(
117                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]),
118            ))
119        },
120    }]
121}
122
123#[cfg(test)]
124#[path = "../unit_tests/rules/hamiltoniancircuit_ilp.rs"]
125mod tests;
problemreductions/rules/hamiltoniancircuit_ilp.rs

problemreductions/rules/
hamiltoniancircuit_ilp.rs
