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_witness(
45            self.target_problem(),
46            target_solution,
47            |value| value.value.is_some(),
48            "target ILP assignment is infeasible",
49        )?;
50
51        crate::rules::ilp_helpers::one_hot_decode_rows(
52            target_solution,
53            self.num_vertices,
54            self.num_groups,
55            0,
56        )
57    }
58}
59
60#[crate::aggregate_reduction(ilp_feasibility)]
61impl crate::rules::AggregateReductionResult for ReductionPITToILP {}
62
63// Source construction requires n divisible by three, so q=n/3 exactly.
64// With h absent unordered pairs: nq variables, n+q+qh rows, and
65// 2nq+2qh terms. Use h<=n(n-1)/2; the empty source has q=0.
66#[reduction(transform = {
67    exact { num_vars = "num_vertices^2 / 3", },
68    upper_bound {
69        max_constraint_magnitude_bits = "2",
70        num_constraints = "4 * num_vertices / 3 + num_vertices^2 * (num_vertices - 1) / 6",
71        num_nonzeros = "(num_vertices^3 + num_vertices^2) / 3",
72    },
73})]
74impl ReduceTo<ILP<bool>> for PartitionIntoTriangles<SimpleGraph> {
75    type Result = ReductionPITToILP;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let num_vertices = self.num_vertices();
79        let q = num_vertices / 3; // number of groups
80        let num_vars = num_vertices * q;
81
82        let mut constraints = Vec::new();
83
84        // Assignment constraints: for each vertex v, Σ_g x_{v,g} = 1
85        for v in 0..num_vertices {
86            let terms: Vec<(usize, i64)> = (0..q).map(|g| (v * q + g, 1)).collect();
87            constraints.push(LinearConstraint::eq(terms, 1));
88        }
89
90        // Group size constraints: for each group g, Σ_v x_{v,g} = 3
91        for g in 0..q {
92            let terms: Vec<(usize, i64)> = (0..num_vertices).map(|v| (v * q + g, 1)).collect();
93            constraints.push(LinearConstraint::eq(terms, 3));
94        }
95
96        // Triangle constraints: for each group g and each non-edge (u,v),
97        // x_{u,g} + x_{v,g} ≤ 1
98        let graph = self.graph();
99        for g in 0..q {
100            for u in 0..num_vertices {
101                for v in (u + 1)..num_vertices {
102                    if !graph.has_edge(u, v) {
103                        constraints.push(LinearConstraint::le(
104                            vec![(u * q + g, 1), (v * q + g, 1)],
105                            1,
106                        ));
107                    }
108                }
109            }
110        }
111
112        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
113            .map_err(Self::target_construction)?;
114
115        Ok(ReductionPITToILP {
116            target,
117            num_vertices,
118            num_groups: q,
119        })
120    }
121}
122
123#[cfg(feature = "example-db")]
124pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
125    vec![crate::example_db::specs::RuleExampleSpec {
126        id: "partitionintotriangles_to_ilp",
127        build: || {
128            // Two triangles: 0-1-2 and 3-4-5
129            let source = PartitionIntoTriangles::new(SimpleGraph::new(
130                6,
131                vec![(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5)],
132            ));
133            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/partitionintotriangles_ilp.rs"]
140mod tests;
problemreductions/rules/partitionintotriangles_ilp.rs

problemreductions/rules/
partitionintotriangles_ilp.rs
