problemreductions/rules/
maximumlikelihoodranking_ilp.rs

1//! Reduction from MaximumLikelihoodRanking to ILP (Integer Linear Programming).
2//!
3//! Binary variables x_{ij} for each pair (i, j) with i < j:
4//! x_{ij} = 1 means item i is ranked before item j.
5//!
6//! Transitivity constraints: for each triple {a, b, c} with a < b < c:
7//!   x_{ab} + x_{bc} - x_{ac} <= 1
8//!   -x_{ab} - x_{bc} + x_{ac} <= 0
9//!
10//! Objective: minimize sum_{i<j} (a_{ji} - a_{ij}) * x_{ij}
11//! (the constant sum_{i<j} a_{ij} does not affect the optimal solution)
12
13use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
14use crate::models::misc::MaximumLikelihoodRanking;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Result of reducing MaximumLikelihoodRanking to ILP.
19#[derive(Debug, Clone)]
20pub struct ReductionMaximumLikelihoodRankingToILP {
21    target: ILP<bool>,
22    /// Number of items in the original problem.
23    n: usize,
24}
25
26/// Map a pair (i, j) with i < j to a variable index.
27fn pair_index(i: usize, j: usize, n: usize) -> usize {
28    debug_assert!(i < j && j < n);
29    // Sum of (n-1) + (n-2) + ... + (n-i) for rows before i, plus offset within row i.
30    // = i*n - i*(i+1)/2 + (j - i - 1)
31    i * n - i * (i + 1) / 2 + (j - i - 1)
32}
33
34impl ReductionResult for ReductionMaximumLikelihoodRankingToILP {
35    type Source = MaximumLikelihoodRanking;
36    type Target = ILP<bool>;
37
38    fn target_problem(&self) -> &ILP<bool> {
39        &self.target
40    }
41
42    fn extract_solution(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
47
48        Ok({
49            let n = self.n;
50            if n == 0 {
51                return Ok(vec![]);
52            }
53
54            // Count how many items are ranked before each item i.
55            // config[i] = number of items ranked before i = rank of item i.
56            let mut config = vec![0usize; n];
57            for i in 0..n {
58                for j in (i + 1)..n {
59                    let idx = pair_index(i, j, n);
60                    if target_solution[idx] == 1 {
61                        // i is before j -> contributes 1 to config[j]
62                        config[j] += 1;
63                    } else {
64                        // j is before i -> contributes 1 to config[i]
65                        config[i] += 1;
66                    }
67                }
68            }
69
70            config
71        })
72    }
73}
74
75#[reduction(
76    transform = exact {
77        max_constraint_magnitude_bits = "1",
78        num_vars = "num_items * (num_items - 1) / 2",
79        num_constraints = "num_items * (num_items - 1) * (num_items - 2) / 3",
80        num_nonzeros = "num_items * (num_items - 1) * (num_items - 2)",
81    },
82)]
83impl ReduceTo<ILP<bool>> for MaximumLikelihoodRanking {
84    type Result = ReductionMaximumLikelihoodRankingToILP;
85
86    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
87        let n = self.num_items();
88        let num_vars = n * (n.saturating_sub(1)) / 2;
89        let matrix = self.matrix();
90
91        // Build objective: minimize sum_{i<j} (a_{ji} - a_{ij}) * x_{ij}
92        let mut objective: Vec<(usize, i64)> = Vec::new();
93        for (i, row_i) in matrix.iter().enumerate() {
94            for j in (i + 1)..n {
95                let difference = matrix[j][i].checked_sub(row_i[j]).ok_or_else(|| {
96                    crate::rules::ReductionError::integer_overflow::<
97                        MaximumLikelihoodRanking,
98                        ILP<bool>,
99                    >("subtracting ranking matrix entries")
100                })?;
101                let coeff = difference;
102                if coeff != 0 {
103                    objective.push((pair_index(i, j, n), coeff));
104                }
105            }
106        }
107
108        // Build transitivity constraints:
109        // For each triple (a, b, c) with a < b < c:
110        //   x_{ab} + x_{bc} - x_{ac} <= 1
111        //   -x_{ab} - x_{bc} + x_{ac} <= 0
112        let mut constraints = Vec::new();
113        for a in 0..n {
114            for b in (a + 1)..n {
115                for c in (b + 1)..n {
116                    let ab = pair_index(a, b, n);
117                    let bc = pair_index(b, c, n);
118                    let ac = pair_index(a, c, n);
119
120                    // x_{ab} + x_{bc} - x_{ac} <= 1
121                    constraints.push(LinearConstraint::le(vec![(ab, 1), (bc, 1), (ac, -1)], 1));
122
123                    // -x_{ab} - x_{bc} + x_{ac} <= 0
124                    constraints.push(LinearConstraint::le(vec![(ab, -1), (bc, -1), (ac, 1)], 0));
125                }
126            }
127        }
128
129        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
130            .map_err(Self::target_construction)?;
131
132        Ok(ReductionMaximumLikelihoodRankingToILP { target, n })
133    }
134}
135
136#[cfg(feature = "example-db")]
137pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
138    vec![crate::example_db::specs::RuleExampleSpec {
139        id: "maximum_likelihood_ranking_to_ilp",
140        build: || {
141            // Use a 3-item matrix for a small example: C(3,2)=3 variables
142            let matrix = vec![vec![0, 3, 2], vec![2, 0, 4], vec![3, 1, 0]];
143            crate::example_db::specs::rule_example_via_ilp(MaximumLikelihoodRanking::new(matrix))
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/maximumlikelihoodranking_ilp.rs"]
150mod tests;
problemreductions/rules/maximumlikelihoodranking_ilp.rs

problemreductions/rules/
maximumlikelihoodranking_ilp.rs
