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_solution(self.target_problem(), target_solution)?;
52
53        Ok({
54            let mut assignment = vec![0usize; self.m];
55            for (var_idx, triple) in self.triples.iter().enumerate() {
56                if target_solution[var_idx] == 1 {
57                    assignment[triple.i] = triple.j;
58                }
59            }
60            assignment
61        })
62    }
63}
64
65#[reduction(
66    transform = upper_bound {
67        num_vars = "num_pairs * num_pairs * num_pairs",
68        num_constraints = "3 * num_pairs",
69    },
70    unavailable = {
71        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
72    }
73)]
74impl ReduceTo<ILP<bool>> for NumericalMatchingWithTargetSums {
75    type Result = ReductionNMTSToILP;
76
77    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
78        let m = self.num_pairs();
79        let sx = self.sizes_x();
80        let sy = self.sizes_y();
81        let targets = self.targets();
82
83        // Enumerate compatible triples: (i, j, k) where s(x_i) + s(y_j) = B_k
84        let mut triples = Vec::new();
85        for (i, &sxi) in sx.iter().enumerate() {
86            for (j, &syj) in sy.iter().enumerate() {
87                for (k, &tk) in targets.iter().enumerate() {
88                    if sxi + syj == tk {
89                        triples.push(CompatibleTriple { i, j, k });
90                    }
91                }
92            }
93        }
94
95        let num_vars = triples.len();
96        let mut constraints = Vec::with_capacity(3 * m);
97
98        // Each x_i in exactly one pair: Σ_{(i,j,k)} z_{i,j,k} = 1 for each i
99        for i in 0..m {
100            let terms: Vec<(usize, i64)> = triples
101                .iter()
102                .enumerate()
103                .filter(|(_, t)| t.i == i)
104                .map(|(idx, _)| (idx, 1))
105                .collect();
106            constraints.push(LinearConstraint::eq(terms, 1));
107        }
108
109        // Each y_j in exactly one pair: Σ_{(i,j,k)} z_{i,j,k} = 1 for each j
110        for j in 0..m {
111            let terms: Vec<(usize, i64)> = triples
112                .iter()
113                .enumerate()
114                .filter(|(_, t)| t.j == j)
115                .map(|(idx, _)| (idx, 1))
116                .collect();
117            constraints.push(LinearConstraint::eq(terms, 1));
118        }
119
120        // Each target k used exactly once: Σ_{(i,j,k)} z_{i,j,k} = 1 for each k
121        for k in 0..m {
122            let terms: Vec<(usize, i64)> = triples
123                .iter()
124                .enumerate()
125                .filter(|(_, t)| t.k == k)
126                .map(|(idx, _)| (idx, 1))
127                .collect();
128            constraints.push(LinearConstraint::eq(terms, 1));
129        }
130
131        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
132            .map_err(Self::target_construction)?;
133
134        Ok(ReductionNMTSToILP { target, triples, m })
135    }
136}
137
138#[cfg(feature = "example-db")]
139pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
140    vec![crate::example_db::specs::RuleExampleSpec {
141        id: "numericalmatchingwithtargetsums_to_ilp",
142        build: || {
143            let source =
144                NumericalMatchingWithTargetSums::new(vec![1, 4, 7], vec![2, 5, 3], vec![3, 7, 12]);
145            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
146        },
147    }]
148}
149
150#[cfg(test)]
151#[path = "../unit_tests/rules/numericalmatchingwithtargetsums_ilp.rs"]
152mod tests;
problemreductions/rules/numericalmatchingwithtargetsums_ilp.rs

problemreductions/rules/
numericalmatchingwithtargetsums_ilp.rs
