problemreductions/rules/
monochromatictriangle_ilp.rs

1//! Reduction from MonochromaticTriangle to ILP.
2//!
3//! Use one binary variable per edge color. Every triangle must use both colors,
4//! encoded as the pair of inequalities `1 <= sum <= 2` over its three incident
5//! edge variables.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::MonochromaticTriangle;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12use std::collections::HashMap;
13
14/// Result of reducing MonochromaticTriangle to ILP.
15#[derive(Debug, Clone)]
16pub struct ReductionMonochromaticTriangleToILP {
17    target: ILP<bool>,
18}
19
20impl ReductionResult for ReductionMonochromaticTriangleToILP {
21    type Source = MonochromaticTriangle<SimpleGraph>;
22    type Target = ILP<bool>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    fn extract_solution(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
33
34        Ok(target_solution.iter().map(|&value| value == 1).collect())
35    }
36}
37
38#[reduction(
39    transform = upper_bound {
40        num_vars = "num_edges",
41        num_constraints = "2 * num_triangles + num_vertices^5 / 8",
42    },
43    unavailable = {
44        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
45    }
46)]
47impl ReduceTo<ILP<bool>> for MonochromaticTriangle<SimpleGraph> {
48    type Result = ReductionMonochromaticTriangleToILP;
49
50    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
51        let mut constraints = Vec::with_capacity(2 * self.num_triangles());
52        for triangle in self.triangles() {
53            let terms: Vec<(usize, i64)> = triangle.iter().map(|&edge_idx| (edge_idx, 1)).collect();
54            constraints.push(LinearConstraint::ge(terms.clone(), 1));
55            constraints.push(LinearConstraint::le(terms, 2));
56        }
57
58        // Every triangle-free two-colouring of K5 consists of two C5s.
59        // Hence each vertex has exactly two incident colour-1 edges in every
60        // K5. These valid equalities strengthen the LP relaxation for all
61        // inputs, independently of how a graph was constructed.
62        let graph = self.graph();
63        let edge_list = self.edge_list();
64        let edge_indices: HashMap<_, _> = edge_list
65            .iter()
66            .enumerate()
67            .map(|(index, &(u, v))| ((u.min(v), u.max(v)), index))
68            .collect();
69        for triangle in self.triangles() {
70            let mut vertices: Vec<_> = triangle
71                .iter()
72                .flat_map(|&edge| [edge_list[edge].0, edge_list[edge].1])
73                .collect();
74            vertices.sort_unstable();
75            vertices.dedup();
76            let [a, b, c] = [vertices[0], vertices[1], vertices[2]];
77            let mut common: Vec<_> = graph
78                .neighbors(c)
79                .into_iter()
80                .filter(|&v| !vertices.contains(&v) && graph.has_edge(a, v) && graph.has_edge(b, v))
81                .collect();
82            common.sort_unstable();
83            common.dedup();
84            // In a K5, the edge opposite this triangle has its majority
85            // colour. All such opposite edges therefore have equal colours.
86            // State these consequences directly so presolve can substitute
87            // colour copies instead of rediscovering the implication by MIP.
88            let mut first_opposite = None;
89            for (index, &d) in common.iter().enumerate() {
90                for &e in &common[index + 1..] {
91                    if graph.has_edge(d, e) {
92                        let opposite = edge_indices[&(d, e)];
93                        if let Some(first) = first_opposite {
94                            constraints
95                                .push(LinearConstraint::eq(vec![(first, 1), (opposite, -1)], 0));
96                        } else {
97                            first_opposite = Some(opposite);
98                        }
99                        // Count each K5's degree equalities only once, using
100                        // its three smallest vertices as the base triangle.
101                        if d <= c {
102                            continue;
103                        }
104                        let clique = [a, b, c, d, e];
105                        for &u in &clique {
106                            let terms = clique
107                                .iter()
108                                .filter(|&&v| v != u)
109                                .map(|&v| (edge_indices[&(u.min(v), u.max(v))], 1))
110                                .collect();
111                            constraints.push(LinearConstraint::eq(terms, 2));
112                        }
113                    }
114                }
115            }
116        }
117
118        Ok(ReductionMonochromaticTriangleToILP {
119            target: ILP::new(
120                self.num_edges(),
121                constraints,
122                vec![],
123                ObjectiveSense::Minimize,
124            )
125            .map_err(Self::target_construction)?,
126        })
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    use crate::topology::SimpleGraph;
133
134    vec![crate::example_db::specs::RuleExampleSpec {
135        id: "monochromatictriangle_to_ilp",
136        build: || {
137            let source = MonochromaticTriangle::new(SimpleGraph::new(
138                4,
139                vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)],
140            ));
141            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
142        },
143    }]
144}
145
146#[cfg(test)]
147#[path = "../unit_tests/rules/monochromatictriangle_ilp.rs"]
148mod tests;
problemreductions/rules/monochromatictriangle_ilp.rs

problemreductions/rules/
monochromatictriangle_ilp.rs
