problemreductions/rules/
numericalmatchingwithtargetsums_ilp.rs

1//! Reduction from NumericalMatchingWithTargetSums to ILP (Integer Linear Programming).
2//!
3//! Binary variables z_{i,j,k} = 1 iff x_i is paired with y_j and assigned
4//! to target k, but only created for compatible triples where
5//! s(x_i) + s(y_j) = B_k.
6//!
7//! Constraints:
8//! - Each x_i in exactly one pair: Σ_{j,k} z_{i,j,k} = 1
9//! - Each y_j in exactly one pair: Σ_{i,k} z_{i,j,k} = 1
10//! - Each target used exactly once: Σ_{i,j} z_{i,j,k} = 1
11//!
12//! Objective: minimize 0 (feasibility).
13
14use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
15use crate::models::misc::NumericalMatchingWithTargetSums;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// A compatible triple (i, j, k) where s(x_i) + s(y_j) = B_k.
20#[derive(Debug, Clone)]
21struct CompatibleTriple {
22    i: usize,
23    j: usize,
24    #[allow(dead_code)]
25    k: usize,
26}
27
28/// Result of reducing NumericalMatchingWithTargetSums to ILP.
29#[derive(Debug, Clone)]
30pub struct ReductionNMTSToILP {
31    target: ILP<bool>,
32    /// Compatible triples, indexed by variable index.
33    triples: Vec<CompatibleTriple>,
34    /// Number of pairs (m).
35    m: usize,
36}
37
38impl ReductionResult for ReductionNMTSToILP {
39    type Source = NumericalMatchingWithTargetSums;
40    type Target = ILP<bool>;
41
42    fn target_problem(&self) -> &ILP<bool> {
43        &self.target
44    }
45
46    /// Extract solution: for each x_i find the y_j it is paired with.
47    fn extract_solution(
48        &self,
49        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
50    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
51        crate::rules::traits::validate_target_witness(
52            self.target_problem(),
53            target_solution,
54            |value| value.value.is_some(),
55            "target ILP assignment is infeasible",
56        )?;
57
58        Ok({
59            let mut assignment = vec![0usize; self.m];
60            for (var_idx, triple) in self.triples.iter().enumerate() {
61                if target_solution[var_idx] == 1 {
62                    assignment[triple.i] = triple.j;
63                }
64            }
65            assignment
66        })
67    }
68}
69
70#[crate::aggregate_reduction(ilp_feasibility)]
71impl crate::rules::AggregateReductionResult for ReductionNMTSToILP {}
72
73#[reduction(transform = upper_bound {
74    max_constraint_magnitude_bits = "1",
75    num_vars = "num_pairs * num_pairs * num_pairs",
76    num_constraints = "3 * num_pairs",
77    num_nonzeros = "(num_pairs * num_pairs * num_pairs) * (3 * num_pairs)",
78})]
79impl ReduceTo<ILP<bool>> for NumericalMatchingWithTargetSums {
80    type Result = ReductionNMTSToILP;
81
82    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
83        let m = self.num_pairs();
84        let sx = self.sizes_x();
85        let sy = self.sizes_y();
86        let targets = self.targets();
87
88        // Enumerate compatible triples: (i, j, k) where s(x_i) + s(y_j) = B_k
89        let mut triples = Vec::new();
90        for (i, &sxi) in sx.iter().enumerate() {
91            for (j, &syj) in sy.iter().enumerate() {
92                for (k, &tk) in targets.iter().enumerate() {
93                    if i128::from(sxi) + i128::from(syj) == i128::from(tk) {
94                        triples.push(CompatibleTriple { i, j, k });
95                    }
96                }
97            }
98        }
99
100        let num_vars = triples.len();
101        let mut constraints = Vec::with_capacity(3 * m);
102
103        // Each x_i in exactly one pair: Σ_{(i,j,k)} z_{i,j,k} = 1 for each i
104        for i in 0..m {
105            let terms: Vec<(usize, i64)> = triples
106                .iter()
107                .enumerate()
108                .filter(|(_, t)| t.i == i)
109                .map(|(idx, _)| (idx, 1))
110                .collect();
111            constraints.push(LinearConstraint::eq(terms, 1));
112        }
113
114        // Each y_j in exactly one pair: Σ_{(i,j,k)} z_{i,j,k} = 1 for each j
115        for j in 0..m {
116            let terms: Vec<(usize, i64)> = triples
117                .iter()
118                .enumerate()
119                .filter(|(_, t)| t.j == j)
120                .map(|(idx, _)| (idx, 1))
121                .collect();
122            constraints.push(LinearConstraint::eq(terms, 1));
123        }
124
125        // Each target k used exactly once: Σ_{(i,j,k)} z_{i,j,k} = 1 for each k
126        for k in 0..m {
127            let terms: Vec<(usize, i64)> = triples
128                .iter()
129                .enumerate()
130                .filter(|(_, t)| t.k == k)
131                .map(|(idx, _)| (idx, 1))
132                .collect();
133            constraints.push(LinearConstraint::eq(terms, 1));
134        }
135
136        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
137            .map_err(Self::target_construction)?;
138
139        Ok(ReductionNMTSToILP { target, triples, m })
140    }
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
145    vec![crate::example_db::specs::RuleExampleSpec {
146        id: "numericalmatchingwithtargetsums_to_ilp",
147        build: || {
148            let source =
149                NumericalMatchingWithTargetSums::new(vec![1, 4, 7], vec![2, 5, 3], vec![3, 7, 12]);
150            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/numericalmatchingwithtargetsums_ilp.rs"]
157mod tests;
problemreductions/rules/numericalmatchingwithtargetsums_ilp.rs

problemreductions/rules/
numericalmatchingwithtargetsums_ilp.rs
