problemreductions/models/misc/
maximum_likelihood_ranking.rs

1//! Maximum Likelihood Ranking problem implementation.
2//!
3//! Given an n x n antisymmetric comparison matrix A where a_ij + a_ji = c
4//! (constant) for every pair and a_ii = 0, find a permutation pi minimizing
5//! the total disagreement cost: sum over all position pairs (i > j) of
6//! a_{pi(i), pi(j)}.  Entries may be negative (e.g. c = 0 gives a
7//! skew-symmetric matrix).
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Min;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "MaximumLikelihoodRanking",
17        display_name: "Maximum Likelihood Ranking",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Find a ranking minimizing total pairwise disagreement cost",
23        fields: &[
24            FieldInfo { name: "matrix", type_name: "Vec<Vec<i64>>", description: "Antisymmetric comparison matrix A (a_ij + a_ji = c, a_ii = 0)" },
25        ],
26    }
27}
28
29/// The Maximum Likelihood Ranking problem.
30///
31/// Given an n x n antisymmetric comparison matrix A where a_ij + a_ji = c
32/// (constant) for every pair and a_ii = 0, find a permutation pi that
33/// minimizes the total disagreement cost: sum_{i > j} a_{pi(i), pi(j)}.
34/// Entries may be negative (e.g. c = 0 gives a skew-symmetric matrix).
35///
36/// Each item is assigned a rank position (0-indexed). The configuration
37/// maps item -> rank: `config[item] = rank`. The permutation pi maps
38/// rank -> item (the inverse of config).
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::misc::MaximumLikelihoodRanking;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// let matrix = vec![
47///     vec![0, 4, 3, 5],
48///     vec![1, 0, 4, 3],
49///     vec![2, 1, 0, 4],
50///     vec![0, 2, 1, 0],
51/// ];
52/// let problem = MaximumLikelihoodRanking::new(matrix);
53/// let solver = BruteForce::new();
54/// let solution = solver.solve(&problem).unwrap();
55/// assert!(solution.is_some());
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct MaximumLikelihoodRanking {
59    matrix: Vec<Vec<i64>>,
60}
61
62impl MaximumLikelihoodRanking {
63    /// Create a new MaximumLikelihoodRanking instance.
64    ///
65    /// # Panics
66    /// Panics if the matrix is not square, if any diagonal element is nonzero,
67    /// or if the pairwise sums `a_ij + a_ji` are not the same constant for
68    /// all `i != j`.
69    pub fn new(matrix: Vec<Vec<i64>>) -> Self {
70        let n = matrix.len();
71        for (i, row) in matrix.iter().enumerate() {
72            assert_eq!(
73                row.len(),
74                n,
75                "matrix must be square: row {i} has length {} but expected {n}",
76                row.len()
77            );
78            assert_eq!(
79                row[i], 0,
80                "diagonal entries must be zero: matrix[{i}][{i}] = {}",
81                row[i]
82            );
83        }
84
85        let mut comparison_count = None;
86        for (i, row) in matrix.iter().enumerate() {
87            for (j, &entry) in row.iter().enumerate().skip(i + 1) {
88                let pair_sum = entry + matrix[j][i];
89                match comparison_count {
90                    None => comparison_count = Some(pair_sum),
91                    Some(expected) => assert_eq!(
92                        pair_sum,
93                        expected,
94                        "all off-diagonal pairs must have the same comparison count: matrix[{i}][{j}] + matrix[{j}][{i}] = {pair_sum}, expected {expected}"
95                    ),
96                }
97            }
98        }
99
100        Self { matrix }
101    }
102
103    /// Returns the comparison matrix.
104    pub fn matrix(&self) -> &Vec<Vec<i64>> {
105        &self.matrix
106    }
107
108    /// Returns the number of items to rank.
109    pub fn num_items(&self) -> usize {
110        self.matrix.len()
111    }
112
113    /// Returns the constant pairwise comparison count `c`.
114    pub fn comparison_count(&self) -> i64 {
115        if self.matrix.len() < 2 {
116            0
117        } else {
118            self.matrix[0][1] + self.matrix[1][0]
119        }
120    }
121}
122
123impl Problem for MaximumLikelihoodRanking {
124    const NAME: &'static str = "MaximumLikelihoodRanking";
125    type Solution = Vec<usize>;
126    type Value = Min<i64>;
127
128    crate::problem_parameters![("num_items", num_items),];
129
130    fn variant() -> Vec<(&'static str, &'static str)> {
131        crate::variant_params![]
132    }
133
134    fn evaluate(
135        &self,
136        config: &Self::Solution,
137    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
138        Ok({
139            let n = self.num_items();
140
141            // Validate config length
142            if config.len() != n {
143                return Err(crate::traits::EvaluationError::InvalidConfiguration(
144                    "ranking length does not match the number of alternatives".into(),
145                ));
146            }
147
148            if config.iter().any(|&rank| rank >= n) {
149                return Err(crate::traits::EvaluationError::InvalidConfiguration(
150                    "ranking contains an out-of-range position".into(),
151                ));
152            }
153
154            // Validate permutation: all values must be distinct and in 0..n
155            let mut seen = vec![false; n];
156            for &rank in config {
157                if rank >= n || seen[rank] {
158                    return Ok(Min(None));
159                }
160                seen[rank] = true;
161            }
162
163            // config[item] = rank position of item
164            // Disagreement cost: for all pairs of items (a, b) where a is
165            // ranked AFTER b (config[a] > config[b]), add matrix[a][b].
166            let mut cost: i64 = 0;
167            for a in 0..n {
168                for b in 0..n {
169                    if a != b && config[a] > config[b] {
170                        cost = cost.checked_add(self.matrix[a][b]).ok_or_else(|| {
171                            crate::traits::EvaluationError::IntegerOverflow(
172                                "summing ranking disagreement costs".into(),
173                            )
174                        })?;
175                    }
176                }
177            }
178
179            Min(Some(cost))
180        })
181    }
182}
183
184impl crate::solvers::BruteForceProblem for MaximumLikelihoodRanking {
185    fn dimensions(&self) -> Vec<usize> {
186        let n = self.num_items();
187        vec![n; n]
188    }
189}
190
191crate::declare_variants! {
192    default MaximumLikelihoodRanking => "num_items * num_items * 2^num_items",
193}
194
195crate::register_brute_force! {
196    MaximumLikelihoodRanking,
197}
198
199#[cfg(feature = "example-db")]
200pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
201    // 4 items with comparison matrix.
202    // Optimal ranking: [0, 1, 2, 3] (identity) gives cost 7.
203    // Let's verify: items ranked in order 0,1,2,3.
204    // Disagreement = sum over (a,b) where config[a] > config[b] of matrix[a][b]
205    // = matrix[1][0] + matrix[2][0] + matrix[2][1] + matrix[3][0] + matrix[3][1] + matrix[3][2]
206    // = 1 + 2 + 1 + 0 + 2 + 1 = 7
207    let matrix = vec![
208        vec![0, 4, 3, 5],
209        vec![1, 0, 4, 3],
210        vec![2, 1, 0, 4],
211        vec![0, 2, 1, 0],
212    ];
213    vec![crate::example_db::specs::ModelExampleSpec {
214        id: "maximum_likelihood_ranking",
215        instance: Box::new(MaximumLikelihoodRanking::new(matrix)),
216        optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
217        optimal_value: serde_json::json!(7),
218    }]
219}
220
221#[cfg(test)]
222#[path = "../../unit_tests/models/misc/maximum_likelihood_ranking.rs"]
223mod tests;
problemreductions/models/misc/maximum_likelihood_ranking.rs

problemreductions/models/misc/
maximum_likelihood_ranking.rs
