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(&self, target_solution: &[usize]) -> Vec<usize> {
43        if self.num_edges == 0 {
44            return vec![];
45        }
46
47        (0..self.num_edges)
48            .map(|edge_idx| {
49                (0..self.num_edges)
50                    .find(|&slot| {
51                        target_solution[self.y_offset + edge_idx * self.num_edges + slot] == 1
52                    })
53                    .unwrap_or(0)
54            })
55            .collect()
56    }
57}
58
59#[reduction(
60    overhead = {
61        num_vars = "num_vertices * num_edges + num_edges + num_edges * num_edges",
62        num_constraints = "num_vertices * num_edges + (num_vertices * (num_vertices - 1) / 2 - num_edges) * num_edges + 3 * num_edges * num_edges + num_edges",
63    }
64)]
65impl ReduceTo<ILP<bool>> for MinimumCoveringByCliques<SimpleGraph> {
66    type Result = ReductionMinimumCoveringByCliquesToILP;
67
68    fn reduce_to(&self) -> Self::Result {
69        let graph = self.graph();
70        let num_vertices = graph.num_vertices();
71        let edges = graph.edges();
72        let num_edges = edges.len();
73        let num_slots = num_edges;
74
75        let x_idx = |vertex: usize, slot: usize| -> usize { vertex * num_slots + slot };
76        let z_offset = num_vertices * num_slots;
77        let z_idx = |slot: usize| -> usize { z_offset + slot };
78        let y_offset = z_offset + num_slots;
79        let y_idx =
80            |edge_idx: usize, slot: usize| -> usize { y_offset + edge_idx * num_slots + slot };
81
82        let mut constraints = Vec::new();
83
84        for slot in 0..num_slots {
85            for u in 0..num_vertices {
86                constraints.push(LinearConstraint::le(
87                    vec![(x_idx(u, slot), 1.0), (z_idx(slot), -1.0)],
88                    0.0,
89                ));
90            }
91        }
92
93        for slot in 0..num_slots {
94            for u in 0..num_vertices {
95                for v in (u + 1)..num_vertices {
96                    if !graph.has_edge(u, v) {
97                        constraints.push(LinearConstraint::le(
98                            vec![(x_idx(u, slot), 1.0), (x_idx(v, slot), 1.0)],
99                            1.0,
100                        ));
101                    }
102                }
103            }
104        }
105
106        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
107            for slot in 0..num_slots {
108                constraints.extend(mccormick_product(
109                    y_idx(edge_idx, slot),
110                    x_idx(u, slot),
111                    x_idx(v, slot),
112                ));
113            }
114        }
115
116        for edge_idx in 0..num_edges {
117            let terms: Vec<(usize, f64)> = (0..num_slots)
118                .map(|slot| (y_idx(edge_idx, slot), 1.0))
119                .collect();
120            constraints.push(LinearConstraint::ge(terms, 1.0));
121        }
122
123        let objective: Vec<(usize, f64)> = (0..num_slots).map(|slot| (z_idx(slot), 1.0)).collect();
124        let target = ILP::new(
125            y_offset + num_edges * num_slots,
126            constraints,
127            objective,
128            ObjectiveSense::Minimize,
129        );
130
131        ReductionMinimumCoveringByCliquesToILP {
132            target,
133            num_edges,
134            y_offset,
135        }
136    }
137}
138
139#[cfg(feature = "example-db")]
140pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
141    vec![crate::example_db::specs::RuleExampleSpec {
142        id: "minimumcoveringbycliques_to_ilp",
143        build: || {
144            let source = MinimumCoveringByCliques::new(SimpleGraph::new(
145                4,
146                vec![(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)],
147            ));
148            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
149        },
150    }]
151}
152
153#[cfg(test)]
154#[path = "../unit_tests/rules/minimumcoveringbycliques_ilp.rs"]
155mod tests;
problemreductions/rules/minimumcoveringbycliques_ilp.rs

problemreductions/rules/
minimumcoveringbycliques_ilp.rs
