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::{ILPCoefficient, 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::variant::VariantParam;
32
33/// Result of reducing MaximumEdgeWeightedKClique to ILP.
34///
35/// Variable layout (all binary):
36/// - `x_v` at index `v` for `v in [0, num_vertices)`,
37/// - `y_uv` at index `num_vertices + e` for the `e`-th graph edge in
38///   `graph.edges()` order.
39#[derive(Debug, Clone)]
40pub struct ReductionMaximumEdgeWeightedKCliqueToILP<W>
41where
42    W: ILPCoefficient,
43{
44    target: ILP<bool, W>,
45    num_vertices: usize,
46}
47
48impl<W> ReductionResult for ReductionMaximumEdgeWeightedKCliqueToILP<W>
49where
50    W: ILPCoefficient + VariantParam,
51{
52    type Source = MaximumEdgeWeightedKClique<W>;
53    type Target = ILP<bool, W>;
54
55    fn target_problem(&self) -> &ILP<bool, W> {
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(
62        &self,
63        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
64    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
65        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
66
67        Ok(target_solution[..self.num_vertices]
68            .iter()
69            .map(|&value| value == 1)
70            .collect())
71    }
72}
73
74fn build_reduction<W>(
75    src: &MaximumEdgeWeightedKClique<W>,
76) -> Result<ReductionMaximumEdgeWeightedKCliqueToILP<W>, crate::rules::ReductionError>
77where
78    W: ILPCoefficient + VariantParam + From<i8>,
79{
80    let n = src.num_vertices();
81    let edges = src.graph().edges();
82    let m = edges.len();
83    let num_vars = n + m;
84    let k =
85        i64::try_from(src.k()).map_err(|_| {
86            crate::rules::ReductionError::integer_overflow::<
87                MaximumEdgeWeightedKClique<W>,
88                ILP<bool, W>,
89            >("encoding the clique cardinality")
90        })?;
91    let x_idx = |v: usize| -> usize { v };
92    let y_idx = |e: usize| -> usize { n + e };
93
94    let mut constraints: Vec<LinearConstraint<W>> = Vec::new();
95
96    // Exact-cardinality constraint: sum_v x_v = k.
97    let cardinality_terms = (0..n).map(|v| (x_idx(v), 1_i8.into())).collect();
98    let k = W::from_integer(k).map_err(|error| {
99        crate::rules::ReductionError::invalid_target::<MaximumEdgeWeightedKClique<W>, ILP<bool, W>>(
100            error.to_string(),
101        )
102    })?;
103    constraints.push(LinearConstraint::eq(cardinality_terms, k));
104
105    // Non-edge clique constraints: x_u + x_v <= 1 for every non-edge.
106    for u in 0..n {
107        for v in (u + 1)..n {
108            if !src.graph().has_edge(u, v) {
109                constraints.push(LinearConstraint::le(
110                    vec![(x_idx(u), 1_i8.into()), (x_idx(v), 1_i8.into())],
111                    1_i8.into(),
112                ));
113            }
114        }
115    }
116
117    // Linking constraints: y_uv = x_u AND x_v via McCormick.
118    for (e, &(u, v)) in edges.iter().enumerate() {
119        constraints.extend(mccormick_product(y_idx(e), x_idx(u), x_idx(v)));
120    }
121
122    // Objective: maximize sum_e w_e * y_e.
123    let objective: Vec<(usize, W)> = src
124        .edge_weights()
125        .iter()
126        .copied()
127        .enumerate()
128        .map(|(e, w)| (y_idx(e), w))
129        .collect();
130
131    let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize).map_err(
132        crate::rules::ReductionError::construction::<MaximumEdgeWeightedKClique<W>, ILP<bool, W>>,
133    )?;
134
135    Ok(ReductionMaximumEdgeWeightedKCliqueToILP {
136        target,
137        num_vertices: n,
138    })
139}
140
141// One cardinality row, at most n(n-1)/2 missing-pair rows, and three
142// product rows per stored edge. Their nonzeros total at most n² + 7m;
143// repeated edges and loops do not subtract from the missing-pair bound.
144#[reduction(transform = {
145    exact {
146        num_vars = "num_vertices + num_edges",
147    },
148    upper_bound {
149        num_constraints = "1 + num_vertices * (num_vertices - 1) / 2 + 3 * num_edges",
150        max_constraint_magnitude_bits = "num_vertices + 1",
151        num_nonzeros = "num_vertices^2 + 7 * num_edges",
152    },
153})]
154impl ReduceTo<ILP<bool>> for MaximumEdgeWeightedKClique<i64> {
155    type Result = ReductionMaximumEdgeWeightedKCliqueToILP<i64>;
156
157    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
158        build_reduction(self)
159    }
160}
161
162#[reduction(transform = {
163    exact {
164        num_vars = "num_vertices + num_edges",
165    },
166    upper_bound {
167        num_constraints = "1 + num_vertices * (num_vertices - 1) / 2 + 3 * num_edges",
168        max_constraint_magnitude_bits = "num_vertices + 1",
169        num_nonzeros = "num_vertices^2 + 7 * num_edges",
170    },
171})]
172impl ReduceTo<ILP<bool, f64>> for MaximumEdgeWeightedKClique<f64> {
173    type Result = ReductionMaximumEdgeWeightedKCliqueToILP<f64>;
174
175    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
176        build_reduction(self)
177    }
178}
179
180#[cfg(feature = "example-db")]
181pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
182    use crate::topology::SimpleGraph;
183    vec![
184        crate::example_db::specs::RuleExampleSpec {
185            id: "exact_maximumedgeweightedkclique_to_ilp",
186            build: || {
187                // Canonical issue #1020 instance: 4 vertices, 5 edges, k = 3.
188                // Optimum induced weight is 5 + 4 + (-1) = 8 on clique {0, 1, 2}.
189                let source = MaximumEdgeWeightedKClique::<i64>::new(
190                    SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]),
191                    vec![5, 4, -1, 1, 0],
192                    3,
193                )
194                .unwrap();
195                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
196            },
197        },
198        crate::example_db::specs::RuleExampleSpec {
199            id: "approximate_maximumedgeweightedkclique_to_ilp",
200            build: || {
201                let source = MaximumEdgeWeightedKClique::<f64>::new(
202                    SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (0, 3), (1, 3)]),
203                    vec![5.0, 4.0, -1.0, 1.0, 0.0],
204                    3,
205                )
206                .unwrap();
207                crate::example_db::specs::rule_example_via_float_ilp::<_, bool>(source)
208            },
209        },
210    ]
211}
212
213#[cfg(test)]
214#[path = "../unit_tests/rules/maximumedgeweightedkclique_ilp.rs"]
215mod tests;
problemreductions/rules/maximumedgeweightedkclique_ilp.rs

problemreductions/rules/
maximumedgeweightedkclique_ilp.rs
