problemreductions/rules/
partitionintocliques_ilp.rs

1//! Reduction from PartitionIntoCliques to binary ILP.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::PartitionIntoCliques;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::{Graph, SimpleGraph};
8
9#[derive(Debug, Clone)]
10pub struct ReductionPartitionIntoCliquesToILP {
11    target: ILP<bool>,
12    num_vertices: usize,
13    num_cliques: usize,
14}
15
16impl ReductionResult for ReductionPartitionIntoCliquesToILP {
17    type Source = PartitionIntoCliques<SimpleGraph>;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_witness(
29            self.target_problem(),
30            target_solution,
31            |value| value.value.is_some(),
32            "target ILP assignment is infeasible",
33        )?;
34
35        (0..self.num_vertices)
36            .map(|vertex| {
37                (0..self.num_cliques)
38                    .find(|&clique| target_solution[vertex * self.num_cliques + clique] == 1)
39                    .ok_or_else(|| {
40                        crate::rules::ExtractionError::invalid(format!(
41                            "target solution does not assign vertex {vertex} to a clique"
42                        ))
43                    })
44            })
45            .collect()
46    }
47}
48
49#[crate::aggregate_reduction(ilp_feasibility)]
50impl crate::rules::AggregateReductionResult for ReductionPartitionIntoCliquesToILP {}
51
52// With k<=n and h absent unordered pairs: n+kh rows and nk+2kh
53// terms. Use h<=n(n-1)/2; loops and parallel edges do not add rows.
54#[reduction(transform = upper_bound {
55    max_constraint_magnitude_bits = "1",
56    num_vars = "num_vertices^2",
57    num_constraints = "num_vertices + num_vertices^2 * (num_vertices - 1) / 2",
58    num_nonzeros = "num_vertices^3",
59})]
60impl ReduceTo<ILP<bool>> for PartitionIntoCliques<SimpleGraph> {
61    type Result = ReductionPartitionIntoCliquesToILP;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let num_vertices = self.num_vertices();
65        let num_cliques = self.num_cliques();
66        let num_vars = num_vertices * num_cliques;
67        let variable = |vertex: usize, clique: usize| vertex * num_cliques + clique;
68        let mut constraints = Vec::new();
69
70        for vertex in 0..num_vertices {
71            constraints.push(LinearConstraint::eq(
72                (0..num_cliques)
73                    .map(|clique| (variable(vertex, clique), 1))
74                    .collect(),
75                1,
76            ));
77        }
78
79        for u in 0..num_vertices {
80            for v in (u + 1)..num_vertices {
81                if !self.graph().has_edge(u, v) {
82                    for clique in 0..num_cliques {
83                        constraints.push(LinearConstraint::le(
84                            vec![(variable(u, clique), 1), (variable(v, clique), 1)],
85                            1,
86                        ));
87                    }
88                }
89            }
90        }
91
92        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
93            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
94
95        Ok(ReductionPartitionIntoCliquesToILP {
96            target,
97            num_vertices,
98            num_cliques,
99        })
100    }
101}
102
103#[cfg(feature = "example-db")]
104pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
105    use crate::export::SolutionPair;
106
107    vec![crate::example_db::specs::RuleExampleSpec {
108        id: "partitionintocliques_to_ilp",
109        build: || {
110            let source = PartitionIntoCliques::new(SimpleGraph::new(3, vec![(0, 1)]), 2);
111            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
112                source,
113                SolutionPair {
114                    source_config: serde_json::json!(vec![0, 0, 1]),
115                    target_config: serde_json::json!(vec![1, 0, 1, 0, 0, 1]),
116                },
117            )
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/partitionintocliques_ilp.rs"]
124mod tests;
problemreductions/rules/partitionintocliques_ilp.rs

problemreductions/rules/
partitionintocliques_ilp.rs
