problemreductions/rules/
partitionintotriangles_ilp.rs

1//! Reduction from PartitionIntoTriangles to ILP (Integer Linear Programming).
2//!
3//! The Partition Into Triangles problem can be formulated as a binary ILP:
4//! - Variables: Binary x_{v,g} (vertex v in group g), one-hot per vertex; q = n/3 groups
5//! - Constraints:
6//!   - Σ_g x_{v,g} = 1 for each vertex v (assignment)
7//!   - Σ_v x_{v,g} = 3 for each group g (exactly 3 vertices per group)
8//!   - For each group g and each non-edge (u,v): x_{u,g} + x_{v,g} ≤ 1 (triangle constraint)
9//! - Objective: Minimize 0 (feasibility)
10//! - Extraction: argmax_g x_{v,g} for each vertex v
11
12use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
13use crate::models::graph::PartitionIntoTriangles;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16use crate::topology::{Graph, SimpleGraph};
17
18/// Result of reducing PartitionIntoTriangles to ILP.
19///
20/// Variable layout: x_{v,g} at index v * q + g.
21/// - v ∈ 0..num_vertices, g ∈ 0..q where q = num_vertices / 3
22///
23/// Total: num_vertices * q = num_vertices^2 / 3 variables.
24#[derive(Debug, Clone)]
25pub struct ReductionPITToILP {
26    target: ILP<bool>,
27    num_vertices: usize,
28    num_groups: usize,
29}
30
31impl ReductionResult for ReductionPITToILP {
32    type Source = PartitionIntoTriangles<SimpleGraph>;
33    type Target = ILP<bool>;
34
35    fn target_problem(&self) -> &ILP<bool> {
36        &self.target
37    }
38
39    /// Extract solution: for each vertex v, find the unique group g where x_{v,g} = 1.
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
45
46        crate::rules::ilp_helpers::one_hot_decode_rows(
47            target_solution,
48            self.num_vertices,
49            self.num_groups,
50            0,
51        )
52    }
53}
54
55#[reduction(
56    transform = upper_bound {
57        num_vars = "num_vertices^2",
58        num_constraints = "num_vertices^2 * num_vertices",
59    },
60    unavailable = {
61        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
62    }
63)]
64impl ReduceTo<ILP<bool>> for PartitionIntoTriangles<SimpleGraph> {
65    type Result = ReductionPITToILP;
66
67    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
68        let num_vertices = self.num_vertices();
69        let q = num_vertices / 3; // number of groups
70        let num_vars = num_vertices * q;
71
72        let mut constraints = Vec::new();
73
74        // Assignment constraints: for each vertex v, Σ_g x_{v,g} = 1
75        for v in 0..num_vertices {
76            let terms: Vec<(usize, i64)> = (0..q).map(|g| (v * q + g, 1)).collect();
77            constraints.push(LinearConstraint::eq(terms, 1));
78        }
79
80        // Group size constraints: for each group g, Σ_v x_{v,g} = 3
81        for g in 0..q {
82            let terms: Vec<(usize, i64)> = (0..num_vertices).map(|v| (v * q + g, 1)).collect();
83            constraints.push(LinearConstraint::eq(terms, 3));
84        }
85
86        // Triangle constraints: for each group g and each non-edge (u,v),
87        // x_{u,g} + x_{v,g} ≤ 1
88        let graph = self.graph();
89        for g in 0..q {
90            for u in 0..num_vertices {
91                for v in (u + 1)..num_vertices {
92                    if !graph.has_edge(u, v) {
93                        constraints.push(LinearConstraint::le(
94                            vec![(u * q + g, 1), (v * q + g, 1)],
95                            1,
96                        ));
97                    }
98                }
99            }
100        }
101
102        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
103            .map_err(Self::target_construction)?;
104
105        Ok(ReductionPITToILP {
106            target,
107            num_vertices,
108            num_groups: q,
109        })
110    }
111}
112
113#[cfg(feature = "example-db")]
114pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
115    vec![crate::example_db::specs::RuleExampleSpec {
116        id: "partitionintotriangles_to_ilp",
117        build: || {
118            // Two triangles: 0-1-2 and 3-4-5
119            let source = PartitionIntoTriangles::new(SimpleGraph::new(
120                6,
121                vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5)],
122            ));
123            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/partitionintotriangles_ilp.rs"]
130mod tests;
problemreductions/rules/partitionintotriangles_ilp.rs

problemreductions/rules/
partitionintotriangles_ilp.rs
