problemreductions/rules/
consistencyofdatabasefrequencytables_ilp.rs

1//! Reduction from ConsistencyOfDatabaseFrequencyTables to ILP.
2//!
3//! The reduction uses a binary one-hot encoding:
4//! - `y_{v,a,x}` is 1 iff object `v` receives value `x` for attribute `a`
5//! - `z_{t,v,x,y}` is 1 iff, for table `t`, object `v` realizes cell `(x, y)`
6//!
7//! The pair-count equalities are linearized with standard McCormick constraints.
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::misc::ConsistencyOfDatabaseFrequencyTables;
11use crate::reduction;
12use crate::rules::ilp_helpers::mccormick_product;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing ConsistencyOfDatabaseFrequencyTables to ILP.
16#[derive(Debug, Clone)]
17pub struct ReductionCDFTToILP {
18    target: ILP<bool>,
19    source: ConsistencyOfDatabaseFrequencyTables,
20}
21
22impl ReductionCDFTToILP {
23    fn assignment_block_size(&self) -> usize {
24        self.source.attribute_domains().iter().sum()
25    }
26
27    fn attribute_offset(&self, attribute: usize) -> usize {
28        self.source.attribute_domains()[..attribute].iter().sum()
29    }
30
31    fn assignment_var_index(&self, object: usize, attribute: usize, value: usize) -> usize {
32        object * self.assignment_block_size() + self.attribute_offset(attribute) + value
33    }
34
35    fn auxiliary_block_start(&self, table_index: usize) -> usize {
36        self.source.num_assignment_indicators()
37            + self.source.frequency_tables()[..table_index]
38                .iter()
39                .map(|table| self.source.num_objects() * table.num_cells())
40                .sum::<usize>()
41    }
42
43    fn auxiliary_var_index(
44        &self,
45        table_index: usize,
46        object: usize,
47        value_a: usize,
48        value_b: usize,
49    ) -> usize {
50        let table = &self.source.frequency_tables()[table_index];
51        let cols = self.source.attribute_domains()[table.attribute_b()];
52        self.auxiliary_block_start(table_index)
53            + object * table.num_cells()
54            + value_a * cols
55            + value_b
56    }
57
58    /// Encode a satisfying source assignment as a concrete ILP variable vector.
59    #[cfg_attr(not(test), allow(dead_code))]
60    pub(crate) fn encode_source_solution(&self, source_solution: &[usize]) -> Vec<i64> {
61        let mut target_solution = vec![0_i64; self.target.num_vars()];
62        let num_attributes = self.source.num_attributes();
63
64        for object in 0..self.source.num_objects() {
65            for attribute in 0..num_attributes {
66                let source_index = object * num_attributes + attribute;
67                let value = source_solution[source_index];
68                let var = self.assignment_var_index(object, attribute, value);
69                target_solution[var] = 1;
70            }
71        }
72
73        for (table_index, table) in self.source.frequency_tables().iter().enumerate() {
74            for object in 0..self.source.num_objects() {
75                let value_a = source_solution[object * num_attributes + table.attribute_a()];
76                let value_b = source_solution[object * num_attributes + table.attribute_b()];
77                let var = self.auxiliary_var_index(table_index, object, value_a, value_b);
78                target_solution[var] = 1;
79            }
80        }
81
82        target_solution
83    }
84}
85
86impl ReductionResult for ReductionCDFTToILP {
87    type Source = ConsistencyOfDatabaseFrequencyTables;
88    type Target = ILP<bool>;
89
90    fn target_problem(&self) -> &ILP<bool> {
91        &self.target
92    }
93
94    fn extract_solution(
95        &self,
96        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
97    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
98        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
99
100        Ok({
101            let mut source_solution = Vec::with_capacity(self.source.num_assignment_variables());
102            for object in 0..self.source.num_objects() {
103                for (attribute, &domain_size) in self.source.attribute_domains().iter().enumerate()
104                {
105                    let mut selected = (0..domain_size).filter(|&candidate| {
106                        target_solution[self.assignment_var_index(object, attribute, candidate)]
107                            == 1
108                    });
109                    let value = match (selected.next(), selected.next()) {
110                        (Some(value), None) => value,
111                        (None, _) => {
112                            return Err(crate::rules::ExtractionError::invalid(format!(
113                                "object {object}, attribute {attribute} has no selected value"
114                            )))
115                        }
116                        (Some(_), Some(_)) => {
117                            return Err(crate::rules::ExtractionError::invalid(format!(
118                                "object {object}, attribute {attribute} has multiple selected values"
119                            )))
120                        }
121                    };
122                    source_solution.push(value);
123                }
124            }
125            source_solution
126        })
127    }
128}
129
130#[reduction(
131    transform = exact {
132        num_vars = "num_objects * total_domain_size + num_objects * num_frequency_cells",
133        num_constraints = "num_objects * num_attributes + num_known_values + num_frequency_cells + 3 * num_objects * num_frequency_cells",
134    },
135    unavailable = {
136        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
137    }
138)]
139impl ReduceTo<ILP<bool>> for ConsistencyOfDatabaseFrequencyTables {
140    type Result = ReductionCDFTToILP;
141
142    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
143        let source = self.clone();
144        let helper = ReductionCDFTToILP {
145            target: ILP::empty(),
146            source: source.clone(),
147        };
148
149        let mut constraints = Vec::with_capacity(
150            source.num_assignment_variables()
151                + source.num_known_values()
152                + source.num_frequency_cells()
153                + 3 * source.num_auxiliary_frequency_indicators(),
154        );
155
156        for object in 0..source.num_objects() {
157            for (attribute, &domain_size) in source.attribute_domains().iter().enumerate() {
158                let terms = (0..domain_size)
159                    .map(|value| (helper.assignment_var_index(object, attribute, value), 1))
160                    .collect();
161                constraints.push(LinearConstraint::eq(terms, 1));
162            }
163        }
164
165        for known_value in source.known_values() {
166            constraints.push(LinearConstraint::eq(
167                vec![(
168                    helper.assignment_var_index(
169                        known_value.object(),
170                        known_value.attribute(),
171                        known_value.value(),
172                    ),
173                    1,
174                )],
175                1,
176            ));
177        }
178
179        for (table_index, table) in source.frequency_tables().iter().enumerate() {
180            let rows = source.attribute_domains()[table.attribute_a()];
181            let cols = source.attribute_domains()[table.attribute_b()];
182
183            for value_a in 0..rows {
184                for value_b in 0..cols {
185                    let count_terms = (0..source.num_objects())
186                        .map(|object| {
187                            (
188                                helper.auxiliary_var_index(table_index, object, value_a, value_b),
189                                1,
190                            )
191                        })
192                        .collect();
193                    let count = table.counts()[value_a][value_b];
194                    constraints.push(LinearConstraint::eq(count_terms, count));
195
196                    for object in 0..source.num_objects() {
197                        let z = helper.auxiliary_var_index(table_index, object, value_a, value_b);
198                        let y_a = helper.assignment_var_index(object, table.attribute_a(), value_a);
199                        let y_b = helper.assignment_var_index(object, table.attribute_b(), value_b);
200
201                        constraints.extend(mccormick_product(z, y_a, y_b));
202                    }
203                }
204            }
205        }
206
207        let target = ILP::new(
208            source.num_assignment_indicators() + source.num_auxiliary_frequency_indicators(),
209            constraints,
210            vec![],
211            ObjectiveSense::Minimize,
212        )
213        .map_err(Self::target_construction)?;
214
215        Ok(ReductionCDFTToILP { target, source })
216    }
217}
218
219#[cfg(feature = "example-db")]
220pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
221    use crate::models::misc::{FrequencyTable, KnownValue};
222
223    vec![crate::example_db::specs::RuleExampleSpec {
224        id: "consistencyofdatabasefrequencytables_to_ilp",
225        build: || {
226            let source = ConsistencyOfDatabaseFrequencyTables::new(
227                6,
228                vec![2, 3, 2],
229                vec![
230                    FrequencyTable::new(0, 1, vec![vec![1, 1, 1], vec![1, 1, 1]]),
231                    FrequencyTable::new(1, 2, vec![vec![1, 1], vec![0, 2], vec![1, 1]]),
232                ],
233                vec![
234                    KnownValue::new(0, 0, 0),
235                    KnownValue::new(3, 0, 1),
236                    KnownValue::new(1, 2, 1),
237                ],
238            );
239            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
240        },
241    }]
242}
243
244#[cfg(test)]
245#[path = "../unit_tests/rules/consistencyofdatabasefrequencytables_ilp.rs"]
246mod tests;
problemreductions/rules/consistencyofdatabasefrequencytables_ilp.rs

problemreductions/rules/
consistencyofdatabasefrequencytables_ilp.rs
