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, i32>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
39        target_solution.to_vec()
40    }
41}
42
43#[reduction(
44    overhead = {
45        num_vars = "num_vertices",
46        num_constraints = "num_vertices^2",
47    }
48)]
49impl ReduceTo<ILP<bool>> for MaximumClique<SimpleGraph, i32> {
50    type Result = ReductionCliqueToILP;
51
52    fn reduce_to(&self) -> Self::Result {
53        let num_vars = self.graph().num_vertices();
54
55        // Constraints: x_u + x_v <= 1 for each NON-EDGE (u, v)
56        // This ensures at most one vertex of each non-edge is selected (i.e., if both
57        // are selected, they must be adjacent, forming a clique)
58        let mut constraints: Vec<LinearConstraint> = Vec::new();
59        for u in 0..num_vars {
60            for v in (u + 1)..num_vars {
61                if !self.graph().has_edge(u, v) {
62                    constraints.push(LinearConstraint::le(vec![(u, 1.0), (v, 1.0)], 1.0));
63                }
64            }
65        }
66
67        // Objective: maximize sum of w_i * x_i (weighted sum of selected vertices)
68        let objective: Vec<(usize, f64)> = self
69            .weights()
70            .iter()
71            .enumerate()
72            .map(|(i, &w)| (i, w as f64))
73            .collect();
74
75        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
76
77        ReductionCliqueToILP { target }
78    }
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/maximumclique_ilp.rs"]
83mod tests;
problemreductions/rules/maximumclique_ilp.rs

problemreductions/rules/
maximumclique_ilp.rs
