problemreductions/rules/
maximumclique_ilp.rs

1//! Reduction from MaximumClique to ILP (Integer Linear Programming).
2//!
3//! The MaximumClique problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per vertex (0 = not selected, 1 = selected)
5//! - Constraints: x_u + x_v <= 1 for each NON-EDGE (u, v) - if two vertices are not adjacent,
6//!   at most one can be in the clique
7//! - Objective: Maximize the sum of weights of selected vertices
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MaximumClique;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing MaximumClique to ILP.
16///
17/// This reduction creates a binary ILP where:
18/// - Each vertex corresponds to a binary variable
19/// - Non-edge constraints ensure at most one endpoint of each non-edge is selected
20/// - The objective maximizes the total weight of selected vertices
21#[derive(Debug, Clone)]
22pub struct ReductionCliqueToILP {
23    target: ILP<bool>,
24}
25
26impl ReductionResult for ReductionCliqueToILP {
27    type Source = MaximumClique<SimpleGraph, i64>;
28    type Target = ILP<bool>;
29
30    fn target_problem(&self) -> &ILP<bool> {
31        &self.target
32    }
33
34    /// Extract solution from ILP back to MaximumClique.
35    ///
36    /// Since the mapping is 1:1 (each vertex maps to one binary variable),
37    /// the solution extraction is simply copying the configuration.
38    fn extract_solution(
39        &self,
40        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
41    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
42        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
43
44        Ok(target_solution.iter().map(|&value| value == 1).collect())
45    }
46}
47
48#[reduction(transform = upper_bound {
49    max_constraint_magnitude_bits = "1",
50    num_vars = "num_vertices",
51    num_constraints = "num_vertices^2",
52    num_nonzeros = "num_vertices * (num_vertices^2)",
53})]
54impl ReduceTo<ILP<bool>> for MaximumClique<SimpleGraph, i64> {
55    type Result = ReductionCliqueToILP;
56
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let num_vars = self.graph().num_vertices();
59
60        // Constraints: x_u + x_v <= 1 for each NON-EDGE (u, v)
61        // This ensures at most one vertex of each non-edge is selected (i.e., if both
62        // are selected, they must be adjacent, forming a clique)
63        let mut constraints: Vec<LinearConstraint> = Vec::new();
64        for u in 0..num_vars {
65            for v in (u + 1)..num_vars {
66                if !self.graph().has_edge(u, v) {
67                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
68                }
69            }
70        }
71
72        // Objective: maximize sum of w_i * x_i (weighted sum of selected vertices)
73        let objective: Vec<(usize, i64)> = self
74            .weights()
75            .iter()
76            .enumerate()
77            .map(|(i, &weight)| (i, weight))
78            .collect();
79
80        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
81            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
82
83        Ok(ReductionCliqueToILP { target })
84    }
85}
86
87#[cfg(feature = "example-db")]
88pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
89    vec![crate::example_db::specs::RuleExampleSpec {
90        id: "maximumclique_to_ilp",
91        build: || {
92            let (n, edges) = crate::topology::small_graphs::octahedral();
93            let source = MaximumClique::new(SimpleGraph::new(n, edges), vec![1i64; 6]);
94            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/maximumclique_ilp.rs"]
101mod tests;
problemreductions/rules/maximumclique_ilp.rs

problemreductions/rules/
maximumclique_ilp.rs
