problemreductions/rules/
expectedretrievalcost_ilp.rs

1//! Reduction from ExpectedRetrievalCost to ILP (Integer Linear Programming).
2//!
3//! The expected retrieval cost objective is quadratic in the assignment variables,
4//! so McCormick linearization is used to produce a binary ILP:
5//!
6//! Variables:
7//! - x_{r,s}: binary, record r placed in sector s (index: r * num_sectors + s)
8//! - z_{r,s,r',s'}: binary product linearization for x_{r,s} * x_{r',s'} (index after x vars)
9//!
10//! Constraints:
11//! - Assignment: Σ_s x_{r,s} = 1 for each r
12//! - McCormick for each (r,s,r',s') product:
13//!   z ≤ x_{r,s}, z ≤ x_{r',s'}, z ≥ x_{r,s} + x_{r',s'} - 1
14//!
15//! Objective: Minimize Σ_{r,s,r',s'} lat(s,s') * p_r * p_{r'} * z_{r,s,r',s'}
16
17use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
18use crate::models::misc::ExpectedRetrievalCost;
19use crate::reduction;
20use crate::rules::ilp_helpers::{mccormick_product, one_hot_decode_rows};
21use crate::rules::traits::{ReduceTo, ReductionResult};
22
23/// Compute the latency distance between sectors on a circular device.
24///
25/// Returns the number of sectors between source and target (not counting source itself),
26/// wrapping around. This matches the `latency_distance` function in the model.
27fn latency_distance(num_sectors: usize, source: usize, target: usize) -> usize {
28    if source < target {
29        target - source - 1
30    } else {
31        num_sectors - source + target - 1
32    }
33}
34
35/// Result of reducing ExpectedRetrievalCost to ILP.
36///
37/// Variable layout:
38/// - x_{r,s} at index r * num_sectors + s  (0..num_records * num_sectors)
39/// - z_{r,s,r',s'} at index num_records*num_sectors + (r * num_sectors + s) * (num_records * num_sectors) + (r' * num_sectors + s')
40///
41/// Total: num_records * num_sectors + (num_records * num_sectors)^2 variables.
42#[derive(Debug, Clone)]
43pub struct ReductionERCToILP {
44    target: ILP<bool, f64>,
45    num_records: usize,
46    num_sectors: usize,
47}
48
49impl ReductionERCToILP {
50    fn x_var(&self, r: usize, s: usize) -> usize {
51        r * self.num_sectors + s
52    }
53
54    fn z_var(&self, r: usize, s: usize, r2: usize, s2: usize) -> usize {
55        let n = self.num_records * self.num_sectors;
56        n + (r * self.num_sectors + s) * n + (r2 * self.num_sectors + s2)
57    }
58}
59
60impl ReductionResult for ReductionERCToILP {
61    type Source = ExpectedRetrievalCost;
62    type Target = ILP<bool, f64>;
63
64    fn target_problem(&self) -> &ILP<bool, f64> {
65        &self.target
66    }
67
68    /// Extract solution: for each record r, find the unique sector s where x_{r,s} = 1.
69    fn extract_solution(
70        &self,
71        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
72    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
73        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
74
75        one_hot_decode_rows(target_solution, self.num_records, self.num_sectors, 0)
76    }
77}
78
79#[reduction(transform = {
80    exact {
81        num_vars = "num_records * num_sectors + num_records^2 * num_sectors^2",
82        num_constraints = "num_records + 3 * num_records^2 * num_sectors^2",
83        num_nonzeros = "7 * num_records^2 * num_sectors^2",
84    },
85    upper_bound {
86        max_constraint_magnitude_bits = "2",
87    },
88})]
89impl ReduceTo<ILP<bool, f64>> for ExpectedRetrievalCost {
90    type Result = ReductionERCToILP;
91
92    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
93        let num_records = self.num_records();
94        let num_sectors = self.num_sectors();
95        let n = num_records * num_sectors; // total x variables
96        let num_vars = n + n * n;
97
98        let result = ReductionERCToILP {
99            target: ILP::empty(),
100            num_records,
101            num_sectors,
102        };
103
104        let mut constraints: Vec<LinearConstraint<f64>> = Vec::new();
105
106        // Assignment constraints: for each record r, Σ_s x_{r,s} = 1
107        for r in 0..num_records {
108            let terms: Vec<(usize, f64)> = (0..num_sectors)
109                .map(|s| (result.x_var(r, s), 1.0))
110                .collect();
111            constraints.push(LinearConstraint::eq(terms, 1.0));
112        }
113
114        // McCormick linearization constraints for each product z_{r,s,r',s'}
115        // z ≤ x_{r,s}      →  z - x_{r,s} ≤ 0
116        // z ≤ x_{r',s'}    →  z - x_{r',s'} ≤ 0
117        // z ≥ x_{r,s} + x_{r',s'} - 1  →  -z + x_{r,s} + x_{r',s'} ≤ 1
118        for r in 0..num_records {
119            for s in 0..num_sectors {
120                for r2 in 0..num_records {
121                    for s2 in 0..num_sectors {
122                        let z = result.z_var(r, s, r2, s2);
123                        let x1 = result.x_var(r, s);
124                        let x2 = result.x_var(r2, s2);
125
126                        constraints.extend(mccormick_product(z, x1, x2));
127                    }
128                }
129            }
130        }
131
132        // Objective: Minimize Σ_{r,s,r',s'} lat(s,s') * p_r * p_{r'} * z_{r,s,r',s'}
133        let probabilities = self.probabilities();
134        let mut objective: Vec<(usize, f64)> = Vec::new();
135        for r in 0..num_records {
136            for s in 0..num_sectors {
137                for r2 in 0..num_records {
138                    for s2 in 0..num_sectors {
139                        let lat = latency_distance(num_sectors, s, s2) as f64;
140                        if lat > 0.0 {
141                            let coeff = lat * probabilities[r] * probabilities[r2];
142                            if coeff.abs() > 0.0 {
143                                let z = result.z_var(r, s, r2, s2);
144                                objective.push((z, coeff));
145                            }
146                        }
147                    }
148                }
149            }
150        }
151
152        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
153            .map_err(Self::target_construction)?;
154
155        Ok(ReductionERCToILP {
156            target,
157            num_records,
158            num_sectors,
159        })
160    }
161}
162
163#[cfg(feature = "example-db")]
164pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
165    use crate::export::SolutionPair;
166
167    vec![crate::example_db::specs::RuleExampleSpec {
168        id: "expectedretrievalcost_to_ilp",
169        build: || {
170            // 2 records with probabilities [0.5, 0.5], 2 sectors
171            // Assignment: record 0 → sector 0, record 1 → sector 1
172            let source = ExpectedRetrievalCost::new(vec![0.5, 0.5], 2).unwrap();
173            // Compute target_config from solver to ensure consistency
174            let reduction: ReductionERCToILP =
175                ReduceTo::<ILP<bool, f64>>::reduce_to(&source).expect("reduction should succeed");
176            let solver = crate::solvers::ILPSolver::new();
177            let target_config = solver
178                .solve(reduction.target_problem())
179                .expect("canonical example should be feasible");
180            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool, f64>>(
181                source,
182                SolutionPair {
183                    source_config: serde_json::json!(vec![0, 1]),
184                    target_config: serde_json::to_value(target_config)
185                        .expect("solution serialization must succeed"),
186                },
187            )
188        },
189    }]
190}
191
192#[cfg(test)]
193#[path = "../unit_tests/rules/expectedretrievalcost_ilp.rs"]
194mod tests;
problemreductions/rules/expectedretrievalcost_ilp.rs

problemreductions/rules/
expectedretrievalcost_ilp.rs
