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(&self, target_solution: &[usize]) -> Vec<usize> {
41        let num_groups = self.num_groups;
42        (0..self.num_vertices)
43            .map(|v| {
44                (0..num_groups)
45                    .find(|&g| {
46                        let idx = v * num_groups + g;
47                        idx < target_solution.len() && target_solution[idx] == 1
48                    })
49                    .unwrap_or(0)
50            })
51            .collect()
52    }
53}
54
55#[reduction(
56    overhead = {
57        num_vars = "num_vertices^2",
58        num_constraints = "num_vertices^2 * num_vertices",
59    }
60)]
61impl ReduceTo<ILP<bool>> for PartitionIntoTriangles<SimpleGraph> {
62    type Result = ReductionPITToILP;
63
64    fn reduce_to(&self) -> Self::Result {
65        let num_vertices = self.num_vertices();
66        let q = num_vertices / 3; // number of groups
67        let num_vars = num_vertices * q;
68
69        let mut constraints = Vec::new();
70
71        // Assignment constraints: for each vertex v, Σ_g x_{v,g} = 1
72        for v in 0..num_vertices {
73            let terms: Vec<(usize, f64)> = (0..q).map(|g| (v * q + g, 1.0)).collect();
74            constraints.push(LinearConstraint::eq(terms, 1.0));
75        }
76
77        // Group size constraints: for each group g, Σ_v x_{v,g} = 3
78        for g in 0..q {
79            let terms: Vec<(usize, f64)> = (0..num_vertices).map(|v| (v * q + g, 1.0)).collect();
80            constraints.push(LinearConstraint::eq(terms, 3.0));
81        }
82
83        // Triangle constraints: for each group g and each non-edge (u,v),
84        // x_{u,g} + x_{v,g} ≤ 1
85        let graph = self.graph();
86        for g in 0..q {
87            for u in 0..num_vertices {
88                for v in (u + 1)..num_vertices {
89                    if !graph.has_edge(u, v) {
90                        constraints.push(LinearConstraint::le(
91                            vec![(u * q + g, 1.0), (v * q + g, 1.0)],
92                            1.0,
93                        ));
94                    }
95                }
96            }
97        }
98
99        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
100
101        ReductionPITToILP {
102            target,
103            num_vertices,
104            num_groups: q,
105        }
106    }
107}
108
109#[cfg(feature = "example-db")]
110pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
111    vec![crate::example_db::specs::RuleExampleSpec {
112        id: "partitionintotriangles_to_ilp",
113        build: || {
114            // Two triangles: 0-1-2 and 3-4-5
115            let source = PartitionIntoTriangles::new(SimpleGraph::new(
116                6,
117                vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5)],
118            ));
119            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/partitionintotriangles_ilp.rs"]
126mod tests;
problemreductions/rules/partitionintotriangles_ilp.rs

problemreductions/rules/
partitionintotriangles_ilp.rs
