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(&self, target_solution: &[usize]) -> Vec<usize> {
43        let n = self.n;
44        if n == 0 {
45            return vec![];
46        }
47
48        // Count how many items are ranked before each item i.
49        // config[i] = number of items ranked before i = rank of item i.
50        let mut config = vec![0usize; n];
51        for i in 0..n {
52            for j in (i + 1)..n {
53                let idx = pair_index(i, j, n);
54                if target_solution[idx] == 1 {
55                    // i is before j -> contributes 1 to config[j]
56                    config[j] += 1;
57                } else {
58                    // j is before i -> contributes 1 to config[i]
59                    config[i] += 1;
60                }
61            }
62        }
63
64        config
65    }
66}
67
68#[reduction(
69    overhead = {
70        num_vars = "num_items * (num_items - 1) / 2",
71        num_constraints = "num_items * (num_items - 1) * (num_items - 2) / 3",
72    }
73)]
74impl ReduceTo<ILP<bool>> for MaximumLikelihoodRanking {
75    type Result = ReductionMaximumLikelihoodRankingToILP;
76
77    fn reduce_to(&self) -> Self::Result {
78        let n = self.num_items();
79        let num_vars = n * (n.saturating_sub(1)) / 2;
80        let matrix = self.matrix();
81
82        // Build objective: minimize sum_{i<j} (a_{ji} - a_{ij}) * x_{ij}
83        let mut objective: Vec<(usize, f64)> = Vec::new();
84        for (i, row_i) in matrix.iter().enumerate() {
85            for j in (i + 1)..n {
86                let coeff = (matrix[j][i] - row_i[j]) as f64;
87                if coeff != 0.0 {
88                    objective.push((pair_index(i, j, n), coeff));
89                }
90            }
91        }
92
93        // Build transitivity constraints:
94        // For each triple (a, b, c) with a < b < c:
95        //   x_{ab} + x_{bc} - x_{ac} <= 1
96        //   -x_{ab} - x_{bc} + x_{ac} <= 0
97        let mut constraints = Vec::new();
98        for a in 0..n {
99            for b in (a + 1)..n {
100                for c in (b + 1)..n {
101                    let ab = pair_index(a, b, n);
102                    let bc = pair_index(b, c, n);
103                    let ac = pair_index(a, c, n);
104
105                    // x_{ab} + x_{bc} - x_{ac} <= 1
106                    constraints.push(LinearConstraint::le(
107                        vec![(ab, 1.0), (bc, 1.0), (ac, -1.0)],
108                        1.0,
109                    ));
110
111                    // -x_{ab} - x_{bc} + x_{ac} <= 0
112                    constraints.push(LinearConstraint::le(
113                        vec![(ab, -1.0), (bc, -1.0), (ac, 1.0)],
114                        0.0,
115                    ));
116                }
117            }
118        }
119
120        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
121
122        ReductionMaximumLikelihoodRankingToILP { target, n }
123    }
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    vec![crate::example_db::specs::RuleExampleSpec {
129        id: "maximum_likelihood_ranking_to_ilp",
130        build: || {
131            // Use a 3-item matrix for a small example: C(3,2)=3 variables
132            let matrix = vec![vec![0, 3, 2], vec![2, 0, 4], vec![3, 1, 0]];
133            crate::example_db::specs::rule_example_via_ilp(MaximumLikelihoodRanking::new(matrix))
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/maximumlikelihoodranking_ilp.rs"]
140mod tests;
problemreductions/rules/maximumlikelihoodranking_ilp.rs

problemreductions/rules/
maximumlikelihoodranking_ilp.rs
