problemreductions/rules/
maximumedgeweightedkclique_ilp.rs

1//! Reduction from MaximumEdgeWeightedKClique to ILP (Integer Linear Programming).
2//!
3//! Binary variables `x_v` per vertex (1 iff vertex `v` is selected) and
4//! `y_uv` per graph edge (1 iff both endpoints are selected). An exact
5//! cardinality constraint forces `|S| = k`. For every non-edge `{u, v}`, the
6//! pair `x_u + x_v <= 1` rules out non-adjacent selected pairs, so the
7//! selected vertex set is forced to be a clique. For every edge `{u, v}`,
8//! the McCormick triple `y_uv <= x_u`, `y_uv <= x_v`,
9//! `y_uv >= x_u + x_v - 1` linearizes the AND of the endpoint variables, so
10//! `y_uv = 1` iff both endpoints are selected. The ILP objective
11//! `max sum_{{u,v} in E} w_uv * y_uv` then matches the induced edge-weight
12//! total of the source instance.
13//!
14//! The lower-bound constraint `y_uv >= x_u + x_v - 1` is required because
15//! edge weights may be negative: without it the ILP could leave a
16//! negative-weight `y_uv` at zero even when both endpoints are selected,
17//! over-reporting the objective.
18//!
19//! Reference: Park, Lee, and Park, "An extended formulation approach to the
20//! edge-weighted maximal clique problem," EJOR 95(3):671--682 (1996);
21//! Gouveia and Martins, "Solving the maximum edge-weight clique problem in
22//! sparse graphs with compact formulations," EURO J. Comput. Optim. 3(1)
23//! (2015).
24
25use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
26use crate::models::graph::MaximumEdgeWeightedKClique;
27use crate::reduction;
28use crate::rules::ilp_helpers::mccormick_product;
29use crate::rules::traits::{ReduceTo, ReductionResult};
30use crate::topology::Graph;
31use crate::types::WeightElement;
32use crate::variant::VariantParam;
33use std::marker::PhantomData;
34
35/// Result of reducing MaximumEdgeWeightedKClique to ILP.
36///
37/// Variable layout (all binary):
38/// - `x_v` at index `v` for `v in [0, num_vertices)`,
39/// - `y_uv` at index `num_vertices + e` for the `e`-th graph edge in
40///   `graph.edges()` order.
41#[derive(Debug, Clone)]
42pub struct ReductionMaximumEdgeWeightedKCliqueToILP<W> {
43    target: ILP<bool>,
44    num_vertices: usize,
45    _marker: PhantomData<W>,
46}
47
48impl<W> ReductionResult for ReductionMaximumEdgeWeightedKCliqueToILP<W>
49where
50    W: WeightElement + VariantParam,
51{
52    type Source = MaximumEdgeWeightedKClique<W>;
53    type Target = ILP<bool>;
54
55    fn target_problem(&self) -> &ILP<bool> {
56        &self.target
57    }
58
59    /// Extract: take the first `num_vertices` entries of the ILP solution.
60    /// They are exactly the binary `x_v` selection variables.
61    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
62        target_solution[..self.num_vertices].to_vec()
63    }
64}
65
66fn build_reduction<W>(
67    src: &MaximumEdgeWeightedKClique<W>,
68    objective_coefficients: Vec<f64>,
69) -> ReductionMaximumEdgeWeightedKCliqueToILP<W>
70where
71    W: WeightElement + VariantParam,
72{
73    let n = src.num_vertices();
74    let edges = src.graph().edges();
75    let m = edges.len();
76    debug_assert_eq!(objective_coefficients.len(), m);
77
78    let num_vars = n + m;
79    let x_idx = |v: usize| -> usize { v };
80    let y_idx = |e: usize| -> usize { n + e };
81
82    let mut constraints: Vec<LinearConstraint> = Vec::new();
83
84    // Exact-cardinality constraint: sum_v x_v = k.
85    let cardinality_terms: Vec<(usize, f64)> = (0..n).map(|v| (x_idx(v), 1.0)).collect();
86    constraints.push(LinearConstraint::eq(cardinality_terms, src.k() as f64));
87
88    // Non-edge clique constraints: x_u + x_v <= 1 for every non-edge.
89    for u in 0..n {
90        for v in (u + 1)..n {
91            if !src.graph().has_edge(u, v) {
92                constraints.push(LinearConstraint::le(
93                    vec![(x_idx(u), 1.0), (x_idx(v), 1.0)],
94                    1.0,
95                ));
96            }
97        }
98    }
99
100    // Linking constraints: y_uv = x_u AND x_v via McCormick.
101    for (e, &(u, v)) in edges.iter().enumerate() {
102        constraints.extend(mccormick_product(y_idx(e), x_idx(u), x_idx(v)));
103    }
104
105    // Objective: maximize sum_e w_e * y_e.
106    let objective: Vec<(usize, f64)> = objective_coefficients
107        .into_iter()
108        .enumerate()
109        .map(|(e, w)| (y_idx(e), w))
110        .collect();
111
112    let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
113
114    ReductionMaximumEdgeWeightedKCliqueToILP {
115        target,
116        num_vertices: n,
117        _marker: PhantomData,
118    }
119}
120
121#[reduction(
122    overhead = {
123        num_vars = "num_vertices + num_edges",
124        num_constraints = "1 + num_vertices * (num_vertices - 1) / 2 + 2 * num_edges",
125    }
126)]
127impl ReduceTo<ILP<bool>> for MaximumEdgeWeightedKClique<i32> {
128    type Result = ReductionMaximumEdgeWeightedKCliqueToILP<i32>;
129
130    fn reduce_to(&self) -> Self::Result {
131        let coefficients: Vec<f64> = self.edge_weights().iter().map(|w| *w as f64).collect();
132        build_reduction(self, coefficients)
133    }
134}
135
136#[reduction(
137    overhead = {
138        num_vars = "num_vertices + num_edges",
139        num_constraints = "1 + num_vertices * (num_vertices - 1) / 2 + 2 * num_edges",
140    }
141)]
142impl ReduceTo<ILP<bool>> for MaximumEdgeWeightedKClique<f64> {
143    type Result = ReductionMaximumEdgeWeightedKCliqueToILP<f64>;
144
145    fn reduce_to(&self) -> Self::Result {
146        let coefficients: Vec<f64> = self.edge_weights().to_vec();
147        build_reduction(self, coefficients)
148    }
149}
150
151#[cfg(feature = "example-db")]
152pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
153    use crate::topology::SimpleGraph;
154    vec![
155        crate::example_db::specs::RuleExampleSpec {
156            id: "maximumedgeweightedkclique_i32_to_ilp",
157            build: || {
158                // Canonical issue #1020 instance: 4 vertices, 5 edges, k = 3.
159                // Optimum induced weight is 5 + 4 + (-1) = 8 on clique {0, 1, 2}.
160                let source = MaximumEdgeWeightedKClique::<i32>::new(
161                    SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]),
162                    vec![5, 4, -1, 1, 0],
163                    3,
164                );
165                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
166            },
167        },
168        crate::example_db::specs::RuleExampleSpec {
169            id: "maximumedgeweightedkclique_f64_to_ilp",
170            build: || {
171                let source = MaximumEdgeWeightedKClique::<f64>::new(
172                    SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]),
173                    vec![5.0, 4.0, -1.0, 1.0, 0.0],
174                    3,
175                );
176                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
177            },
178        },
179    ]
180}
181
182#[cfg(test)]
183#[path = "../unit_tests/rules/maximumedgeweightedkclique_ilp.rs"]
184mod tests;
problemreductions/rules/maximumedgeweightedkclique_ilp.rs

problemreductions/rules/
maximumedgeweightedkclique_ilp.rs
