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

problemreductions/rules/
numericalmatchingwithtargetsums_ilp.rs
