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::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing ConsistencyOfDatabaseFrequencyTables to ILP.
15#[derive(Debug, Clone)]
16pub struct ReductionCDFTToILP {
17    target: ILP<bool>,
18    source: ConsistencyOfDatabaseFrequencyTables,
19}
20
21impl ReductionCDFTToILP {
22    fn assignment_block_size(&self) -> usize {
23        self.source.attribute_domains().iter().sum()
24    }
25
26    fn attribute_offset(&self, attribute: usize) -> usize {
27        self.source.attribute_domains()[..attribute].iter().sum()
28    }
29
30    fn assignment_var_index(&self, object: usize, attribute: usize, value: usize) -> usize {
31        object * self.assignment_block_size() + self.attribute_offset(attribute) + value
32    }
33
34    fn auxiliary_block_start(&self, table_index: usize) -> usize {
35        self.source.num_assignment_indicators()
36            + self.source.frequency_tables()[..table_index]
37                .iter()
38                .map(|table| self.source.num_objects() * table.num_cells())
39                .sum::<usize>()
40    }
41
42    fn auxiliary_var_index(
43        &self,
44        table_index: usize,
45        object: usize,
46        value_a: usize,
47        value_b: usize,
48    ) -> usize {
49        let table = &self.source.frequency_tables()[table_index];
50        let cols = self.source.attribute_domains()[table.attribute_b()];
51        self.auxiliary_block_start(table_index)
52            + object * table.num_cells()
53            + value_a * cols
54            + value_b
55    }
56
57    /// Encode a satisfying source assignment as a concrete ILP variable vector.
58    #[cfg_attr(not(test), allow(dead_code))]
59    pub(crate) fn encode_source_solution(&self, source_solution: &[usize]) -> Vec<usize> {
60        let mut target_solution = vec![0usize; self.target.num_vars];
61        let num_attributes = self.source.num_attributes();
62
63        for object in 0..self.source.num_objects() {
64            for attribute in 0..num_attributes {
65                let source_index = object * num_attributes + attribute;
66                let value = source_solution[source_index];
67                let var = self.assignment_var_index(object, attribute, value);
68                target_solution[var] = 1;
69            }
70        }
71
72        for (table_index, table) in self.source.frequency_tables().iter().enumerate() {
73            for object in 0..self.source.num_objects() {
74                let value_a = source_solution[object * num_attributes + table.attribute_a()];
75                let value_b = source_solution[object * num_attributes + table.attribute_b()];
76                let var = self.auxiliary_var_index(table_index, object, value_a, value_b);
77                target_solution[var] = 1;
78            }
79        }
80
81        target_solution
82    }
83}
84
85impl ReductionResult for ReductionCDFTToILP {
86    type Source = ConsistencyOfDatabaseFrequencyTables;
87    type Target = ILP<bool>;
88
89    fn target_problem(&self) -> &ILP<bool> {
90        &self.target
91    }
92
93    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
94        let mut source_solution = Vec::with_capacity(self.source.num_assignment_variables());
95        for object in 0..self.source.num_objects() {
96            for (attribute, &domain_size) in self.source.attribute_domains().iter().enumerate() {
97                let value = (0..domain_size)
98                    .find(|&candidate| {
99                        target_solution
100                            .get(self.assignment_var_index(object, attribute, candidate))
101                            .copied()
102                            .unwrap_or(0)
103                            == 1
104                    })
105                    .unwrap_or(0);
106                source_solution.push(value);
107            }
108        }
109        source_solution
110    }
111}
112
113#[reduction(
114    overhead = {
115        num_vars = "num_assignment_indicators + num_auxiliary_frequency_indicators",
116        num_constraints = "num_assignment_variables + num_known_values + num_frequency_cells + 3 * num_auxiliary_frequency_indicators",
117    }
118)]
119impl ReduceTo<ILP<bool>> for ConsistencyOfDatabaseFrequencyTables {
120    type Result = ReductionCDFTToILP;
121
122    fn reduce_to(&self) -> Self::Result {
123        let source = self.clone();
124        let helper = ReductionCDFTToILP {
125            target: ILP::empty(),
126            source: source.clone(),
127        };
128
129        let mut constraints = Vec::with_capacity(
130            source.num_assignment_variables()
131                + source.num_known_values()
132                + source.num_frequency_cells()
133                + 3 * source.num_auxiliary_frequency_indicators(),
134        );
135
136        for object in 0..source.num_objects() {
137            for (attribute, &domain_size) in source.attribute_domains().iter().enumerate() {
138                let terms = (0..domain_size)
139                    .map(|value| (helper.assignment_var_index(object, attribute, value), 1.0))
140                    .collect();
141                constraints.push(LinearConstraint::eq(terms, 1.0));
142            }
143        }
144
145        for known_value in source.known_values() {
146            constraints.push(LinearConstraint::eq(
147                vec![(
148                    helper.assignment_var_index(
149                        known_value.object(),
150                        known_value.attribute(),
151                        known_value.value(),
152                    ),
153                    1.0,
154                )],
155                1.0,
156            ));
157        }
158
159        for (table_index, table) in source.frequency_tables().iter().enumerate() {
160            let rows = source.attribute_domains()[table.attribute_a()];
161            let cols = source.attribute_domains()[table.attribute_b()];
162
163            for value_a in 0..rows {
164                for value_b in 0..cols {
165                    let count_terms = (0..source.num_objects())
166                        .map(|object| {
167                            (
168                                helper.auxiliary_var_index(table_index, object, value_a, value_b),
169                                1.0,
170                            )
171                        })
172                        .collect();
173                    constraints.push(LinearConstraint::eq(
174                        count_terms,
175                        table.counts()[value_a][value_b] as f64,
176                    ));
177
178                    for object in 0..source.num_objects() {
179                        let z = helper.auxiliary_var_index(table_index, object, value_a, value_b);
180                        let y_a = helper.assignment_var_index(object, table.attribute_a(), value_a);
181                        let y_b = helper.assignment_var_index(object, table.attribute_b(), value_b);
182
183                        constraints.push(LinearConstraint::le(vec![(z, 1.0), (y_a, -1.0)], 0.0));
184                        constraints.push(LinearConstraint::le(vec![(z, 1.0), (y_b, -1.0)], 0.0));
185                        constraints.push(LinearConstraint::ge(
186                            vec![(z, 1.0), (y_a, -1.0), (y_b, -1.0)],
187                            -1.0,
188                        ));
189                    }
190                }
191            }
192        }
193
194        let target = ILP::new(
195            source.num_assignment_indicators() + source.num_auxiliary_frequency_indicators(),
196            constraints,
197            vec![],
198            ObjectiveSense::Minimize,
199        );
200
201        ReductionCDFTToILP { target, source }
202    }
203}
204
205#[cfg(feature = "example-db")]
206pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
207    use crate::models::misc::{FrequencyTable, KnownValue};
208
209    vec![crate::example_db::specs::RuleExampleSpec {
210        id: "consistencyofdatabasefrequencytables_to_ilp",
211        build: || {
212            let source = ConsistencyOfDatabaseFrequencyTables::new(
213                6,
214                vec![2, 3, 2],
215                vec![
216                    FrequencyTable::new(0, 1, vec![vec![1, 1, 1], vec![1, 1, 1]]),
217                    FrequencyTable::new(1, 2, vec![vec![1, 1], vec![0, 2], vec![1, 1]]),
218                ],
219                vec![
220                    KnownValue::new(0, 0, 0),
221                    KnownValue::new(3, 0, 1),
222                    KnownValue::new(1, 2, 1),
223                ],
224            );
225            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
226        },
227    }]
228}
229
230#[cfg(test)]
231#[path = "../unit_tests/rules/consistencyofdatabasefrequencytables_ilp.rs"]
232mod tests;
problemreductions/rules/consistencyofdatabasefrequencytables_ilp.rs

problemreductions/rules/
consistencyofdatabasefrequencytables_ilp.rs
