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(
49    transform = upper_bound {
50        num_vars = "num_vertices",
51        num_constraints = "num_vertices^2",
52    },
53    unavailable = {
54        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
55    }
56)]
57impl ReduceTo<ILP<bool>> for MaximumClique<SimpleGraph, i64> {
58    type Result = ReductionCliqueToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let num_vars = self.graph().num_vertices();
62
63        // Constraints: x_u + x_v <= 1 for each NON-EDGE (u, v)
64        // This ensures at most one vertex of each non-edge is selected (i.e., if both
65        // are selected, they must be adjacent, forming a clique)
66        let mut constraints: Vec<LinearConstraint> = Vec::new();
67        for u in 0..num_vars {
68            for v in (u + 1)..num_vars {
69                if !self.graph().has_edge(u, v) {
70                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
71                }
72            }
73        }
74
75        // Objective: maximize sum of w_i * x_i (weighted sum of selected vertices)
76        let objective: Vec<(usize, i64)> = self
77            .weights()
78            .iter()
79            .enumerate()
80            .map(|(i, &weight)| (i, weight))
81            .collect();
82
83        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
84            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
85
86        Ok(ReductionCliqueToILP { target })
87    }
88}
89
90#[cfg(feature = "example-db")]
91pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "maximumclique_to_ilp",
94        build: || {
95            let (n, edges) = crate::topology::small_graphs::octahedral();
96            let source = MaximumClique::new(SimpleGraph::new(n, edges), vec![1i64; 6]);
97            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/maximumclique_ilp.rs"]
104mod tests;
problemreductions/rules/maximumclique_ilp.rs

problemreductions/rules/
maximumclique_ilp.rs
