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(
80    transform = 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    },
84    unavailable = {
85        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
86    }
87)]
88impl ReduceTo<ILP<bool, f64>> for ExpectedRetrievalCost {
89    type Result = ReductionERCToILP;
90
91    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
92        let num_records = self.num_records();
93        let num_sectors = self.num_sectors();
94        let n = num_records * num_sectors; // total x variables
95        let num_vars = n + n * n;
96
97        let result = ReductionERCToILP {
98            target: ILP::empty(),
99            num_records,
100            num_sectors,
101        };
102
103        let mut constraints: Vec<LinearConstraint<f64>> = Vec::new();
104
105        // Assignment constraints: for each record r, Σ_s x_{r,s} = 1
106        for r in 0..num_records {
107            let terms: Vec<(usize, f64)> = (0..num_sectors)
108                .map(|s| (result.x_var(r, s), 1.0))
109                .collect();
110            constraints.push(LinearConstraint::eq(terms, 1.0));
111        }
112
113        // McCormick linearization constraints for each product z_{r,s,r',s'}
114        // z ≤ x_{r,s}      →  z - x_{r,s} ≤ 0
115        // z ≤ x_{r',s'}    →  z - x_{r',s'} ≤ 0
116        // z ≥ x_{r,s} + x_{r',s'} - 1  →  -z + x_{r,s} + x_{r',s'} ≤ 1
117        for r in 0..num_records {
118            for s in 0..num_sectors {
119                for r2 in 0..num_records {
120                    for s2 in 0..num_sectors {
121                        let z = result.z_var(r, s, r2, s2);
122                        let x1 = result.x_var(r, s);
123                        let x2 = result.x_var(r2, s2);
124
125                        constraints.extend(mccormick_product(z, x1, x2));
126                    }
127                }
128            }
129        }
130
131        // Objective: Minimize Σ_{r,s,r',s'} lat(s,s') * p_r * p_{r'} * z_{r,s,r',s'}
132        let probabilities = self.probabilities();
133        let mut objective: Vec<(usize, f64)> = Vec::new();
134        for r in 0..num_records {
135            for s in 0..num_sectors {
136                for r2 in 0..num_records {
137                    for s2 in 0..num_sectors {
138                        let lat = latency_distance(num_sectors, s, s2) as f64;
139                        if lat > 0.0 {
140                            let coeff = lat * probabilities[r] * probabilities[r2];
141                            if coeff.abs() > 0.0 {
142                                let z = result.z_var(r, s, r2, s2);
143                                objective.push((z, coeff));
144                            }
145                        }
146                    }
147                }
148            }
149        }
150
151        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
152            .map_err(Self::target_construction)?;
153
154        Ok(ReductionERCToILP {
155            target,
156            num_records,
157            num_sectors,
158        })
159    }
160}
161
162#[cfg(feature = "example-db")]
163pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
164    use crate::export::SolutionPair;
165
166    vec![crate::example_db::specs::RuleExampleSpec {
167        id: "expectedretrievalcost_to_ilp",
168        build: || {
169            // 2 records with probabilities [0.5, 0.5], 2 sectors
170            // Assignment: record 0 → sector 0, record 1 → sector 1
171            let source = ExpectedRetrievalCost::new(vec![0.5, 0.5], 2).unwrap();
172            // Compute target_config from solver to ensure consistency
173            let reduction: ReductionERCToILP =
174                ReduceTo::<ILP<bool, f64>>::reduce_to(&source).expect("reduction should succeed");
175            let solver = crate::solvers::ILPSolver::new();
176            let target_config = solver
177                .solve(reduction.target_problem())
178                .expect("canonical example should be feasible");
179            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool, f64>>(
180                source,
181                SolutionPair {
182                    source_config: serde_json::json!(vec![0, 1]),
183                    target_config: serde_json::to_value(target_config)
184                        .expect("solution serialization must succeed"),
185                },
186            )
187        },
188    }]
189}
190
191#[cfg(test)]
192#[path = "../unit_tests/rules/expectedretrievalcost_ilp.rs"]
193mod tests;
problemreductions/rules/expectedretrievalcost_ilp.rs

problemreductions/rules/
expectedretrievalcost_ilp.rs
