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// With n vertices and m stored edges, activation, missing-pair, product, and
65// coverage blocks contribute nm, at most n(n-1)m/2, 3m², and m rows.
66// Their nonzeros are bounded by 2nm, n(n-1)m, 7m², and m². Stored edges may repeat.
67#[reduction(transform = {
68    exact {
69        num_vars = "num_vertices * num_edges + num_edges + num_edges * num_edges",
70    },
71    upper_bound {
72        num_constraints = "num_vertices * num_edges + num_vertices * (num_vertices - 1) / 2 * num_edges + 3 * num_edges^2 + num_edges",
73        max_constraint_magnitude_bits = "2",
74        num_nonzeros = "2 * num_vertices * num_edges + num_vertices * (num_vertices - 1) * num_edges + 8 * num_edges^2",
75    },
76})]
77impl ReduceTo<ILP<bool>> for MinimumCoveringByCliques<SimpleGraph> {
78    type Result = ReductionMinimumCoveringByCliquesToILP;
79
80    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
81        let graph = self.graph();
82        let num_vertices = graph.num_vertices();
83        let edges = graph.edges();
84        let num_edges = edges.len();
85        let num_slots = num_edges;
86
87        let x_idx = |vertex: usize, slot: usize| -> usize { vertex * num_slots + slot };
88        let z_offset = num_vertices * num_slots;
89        let z_idx = |slot: usize| -> usize { z_offset + slot };
90        let y_offset = z_offset + num_slots;
91        let y_idx =
92            |edge_idx: usize, slot: usize| -> usize { y_offset + edge_idx * num_slots + slot };
93
94        let mut constraints = Vec::new();
95
96        for slot in 0..num_slots {
97            for u in 0..num_vertices {
98                constraints.push(LinearConstraint::le(
99                    vec![(x_idx(u, slot), 1), (z_idx(slot), -1)],
100                    0,
101                ));
102            }
103        }
104
105        for slot in 0..num_slots {
106            for u in 0..num_vertices {
107                for v in (u + 1)..num_vertices {
108                    if !graph.has_edge(u, v) {
109                        constraints.push(LinearConstraint::le(
110                            vec![(x_idx(u, slot), 1), (x_idx(v, slot), 1)],
111                            1,
112                        ));
113                    }
114                }
115            }
116        }
117
118        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
119            for slot in 0..num_slots {
120                constraints.extend(mccormick_product(
121                    y_idx(edge_idx, slot),
122                    x_idx(u, slot),
123                    x_idx(v, slot),
124                ));
125            }
126        }
127
128        for edge_idx in 0..num_edges {
129            let terms: Vec<(usize, i64)> = (0..num_slots)
130                .map(|slot| (y_idx(edge_idx, slot), 1))
131                .collect();
132            constraints.push(LinearConstraint::ge(terms, 1));
133        }
134
135        let objective: Vec<(usize, i64)> = (0..num_slots).map(|slot| (z_idx(slot), 1)).collect();
136        let target = ILP::new(
137            y_offset + num_edges * num_slots,
138            constraints,
139            objective,
140            ObjectiveSense::Minimize,
141        )
142        .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
143
144        Ok(ReductionMinimumCoveringByCliquesToILP {
145            target,
146            num_edges,
147            y_offset,
148        })
149    }
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
154    vec![crate::example_db::specs::RuleExampleSpec {
155        id: "minimumcoveringbycliques_to_ilp",
156        build: || {
157            let source = MinimumCoveringByCliques::new(SimpleGraph::new(
158                4,
159                vec![(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)],
160            ));
161            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
162        },
163    }]
164}
165
166#[cfg(test)]
167#[path = "../unit_tests/rules/minimumcoveringbycliques_ilp.rs"]
168mod tests;
problemreductions/rules/minimumcoveringbycliques_ilp.rs

problemreductions/rules/
minimumcoveringbycliques_ilp.rs
