problemreductions/rules/
minimumcoveringbycliques_ilp.rs

1//! Reduction from MinimumCoveringByCliques to ILP.
2//!
3//! We use one potential clique slot per source edge, matching the source-model
4//! encoding where each edge is assigned a group label in `[0, |E|)`.
5//!
6//! Variables:
7//! - `x_(v,k)`: vertex `v` is selected into clique slot `k`
8//! - `z_k`: clique slot `k` is active
9//! - `y_(e,k)`: edge `e = {u,v}` is covered by slot `k`, linearized as
10//!   `x_(u,k) * x_(v,k)`
11//!
12//! Constraints:
13//! - Non-edges cannot appear together in the same clique slot
14//! - `x_(v,k) <= z_k`
15//! - Every edge is covered by at least one clique slot
16//! - McCormick constraints enforce `y_(e,k) = x_(u,k) * x_(v,k)`
17//!
18//! Objective: minimize the number of active clique slots.
19
20use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
21use crate::models::graph::MinimumCoveringByCliques;
22use crate::reduction;
23use crate::rules::ilp_helpers::mccormick_product;
24use crate::rules::traits::{ReduceTo, ReductionResult};
25use crate::topology::{Graph, SimpleGraph};
26
27#[derive(Debug, Clone)]
28pub struct ReductionMinimumCoveringByCliquesToILP {
29    target: ILP<bool>,
30    num_edges: usize,
31    y_offset: usize,
32}
33
34impl ReductionResult for ReductionMinimumCoveringByCliquesToILP {
35    type Source = MinimumCoveringByCliques<SimpleGraph>;
36    type Target = ILP<bool>;
37
38    fn target_problem(&self) -> &ILP<bool> {
39        &self.target
40    }
41
42    fn extract_solution(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
47
48        (0..self.num_edges)
49            .map(|edge| {
50                (0..self.num_edges)
51                    .find(|&clique| {
52                        target_solution[self.y_offset + edge * self.num_edges + clique] == 1
53                    })
54                    .ok_or_else(|| {
55                        crate::rules::ExtractionError::invalid(format!(
56                            "edge {edge} is not covered by any clique"
57                        ))
58                    })
59            })
60            .collect()
61    }
62}
63
64#[reduction(
65    transform = exact {
66        num_vars = "num_vertices * num_edges + num_edges + num_edges * num_edges",
67        num_constraints = "num_vertices * num_edges + (num_vertices * (num_vertices - 1) / 2 - num_edges) * num_edges + 3 * num_edges * num_edges + num_edges",
68    },
69    unavailable = {
70        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
71    }
72)]
73impl ReduceTo<ILP<bool>> for MinimumCoveringByCliques<SimpleGraph> {
74    type Result = ReductionMinimumCoveringByCliquesToILP;
75
76    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
77        let graph = self.graph();
78        let num_vertices = graph.num_vertices();
79        let edges = graph.edges();
80        let num_edges = edges.len();
81        let num_slots = num_edges;
82
83        let x_idx = |vertex: usize, slot: usize| -> usize { vertex * num_slots + slot };
84        let z_offset = num_vertices * num_slots;
85        let z_idx = |slot: usize| -> usize { z_offset + slot };
86        let y_offset = z_offset + num_slots;
87        let y_idx =
88            |edge_idx: usize, slot: usize| -> usize { y_offset + edge_idx * num_slots + slot };
89
90        let mut constraints = Vec::new();
91
92        for slot in 0..num_slots {
93            for u in 0..num_vertices {
94                constraints.push(LinearConstraint::le(
95                    vec![(x_idx(u, slot), 1), (z_idx(slot), -1)],
96                    0,
97                ));
98            }
99        }
100
101        for slot in 0..num_slots {
102            for u in 0..num_vertices {
103                for v in (u + 1)..num_vertices {
104                    if !graph.has_edge(u, v) {
105                        constraints.push(LinearConstraint::le(
106                            vec![(x_idx(u, slot), 1), (x_idx(v, slot), 1)],
107                            1,
108                        ));
109                    }
110                }
111            }
112        }
113
114        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
115            for slot in 0..num_slots {
116                constraints.extend(mccormick_product(
117                    y_idx(edge_idx, slot),
118                    x_idx(u, slot),
119                    x_idx(v, slot),
120                ));
121            }
122        }
123
124        for edge_idx in 0..num_edges {
125            let terms: Vec<(usize, i64)> = (0..num_slots)
126                .map(|slot| (y_idx(edge_idx, slot), 1))
127                .collect();
128            constraints.push(LinearConstraint::ge(terms, 1));
129        }
130
131        let objective: Vec<(usize, i64)> = (0..num_slots).map(|slot| (z_idx(slot), 1)).collect();
132        let target = ILP::new(
133            y_offset + num_edges * num_slots,
134            constraints,
135            objective,
136            ObjectiveSense::Minimize,
137        )
138        .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
139
140        Ok(ReductionMinimumCoveringByCliquesToILP {
141            target,
142            num_edges,
143            y_offset,
144        })
145    }
146}
147
148#[cfg(feature = "example-db")]
149pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
150    vec![crate::example_db::specs::RuleExampleSpec {
151        id: "minimumcoveringbycliques_to_ilp",
152        build: || {
153            let source = MinimumCoveringByCliques::new(SimpleGraph::new(
154                4,
155                vec![(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)],
156            ));
157            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
158        },
159    }]
160}
161
162#[cfg(test)]
163#[path = "../unit_tests/rules/minimumcoveringbycliques_ilp.rs"]
164mod tests;
problemreductions/rules/minimumcoveringbycliques_ilp.rs

problemreductions/rules/
minimumcoveringbycliques_ilp.rs
