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)]
58#[serde(try_from = "MaximumLikelihoodRankingData")]
59pub struct MaximumLikelihoodRanking {
60    matrix: Vec<Vec<i64>>,
61}
62
63#[derive(Deserialize)]
64struct MaximumLikelihoodRankingData {
65    matrix: Vec<Vec<i64>>,
66}
67
68impl TryFrom<MaximumLikelihoodRankingData> for MaximumLikelihoodRanking {
69    type Error = crate::registry::ConstructionError;
70
71    fn try_from(data: MaximumLikelihoodRankingData) -> Result<Self, Self::Error> {
72        Self::try_new(data.matrix)
73    }
74}
75
76impl MaximumLikelihoodRanking {
77    /// Create a new MaximumLikelihoodRanking instance.
78    ///
79    /// # Panics
80    /// Panics if the matrix is not square, if any diagonal element is nonzero,
81    /// or if the pairwise sums `a_ij + a_ji` are not the same constant for
82    /// all `i != j`.
83    pub fn new(matrix: Vec<Vec<i64>>) -> Self {
84        Self::try_new(matrix).unwrap_or_else(|error| panic!("{error}"))
85    }
86
87    fn try_new(matrix: Vec<Vec<i64>>) -> Result<Self, crate::registry::ConstructionError> {
88        let n = matrix.len();
89        for (i, row) in matrix.iter().enumerate() {
90            if row.len() != n {
91                return Err(format!(
92                    "matrix must be square: row {i} has length {} but expected {n}",
93                    row.len()
94                )
95                .into());
96            }
97            if row[i] != 0 {
98                return Err(format!(
99                    "diagonal entries must be zero: matrix[{i}][{i}] = {}",
100                    row[i]
101                )
102                .into());
103            }
104        }
105
106        let mut comparison_count = None;
107        for (i, row) in matrix.iter().enumerate() {
108            for (j, &entry) in row.iter().enumerate().skip(i + 1) {
109                let pair_sum = entry.checked_add(matrix[j][i]).ok_or_else(|| {
110                    crate::registry::ConstructionError::IntegerOverflow(
111                        "computing the pairwise comparison count".into(),
112                    )
113                })?;
114                match comparison_count {
115                    None => comparison_count = Some(pair_sum),
116                    Some(expected) => {
117                        if pair_sum != expected {
118                            return Err(format!("all off-diagonal pairs must have the same comparison count: matrix[{i}][{j}] + matrix[{j}][{i}] = {pair_sum}, expected {expected}").into());
119                        }
120                    }
121                }
122            }
123        }
124
125        Ok(Self { matrix })
126    }
127
128    /// Returns the comparison matrix.
129    pub fn matrix(&self) -> &Vec<Vec<i64>> {
130        &self.matrix
131    }
132
133    /// Returns the number of items to rank.
134    pub fn num_items(&self) -> usize {
135        self.matrix.len()
136    }
137
138    /// Returns the constant pairwise comparison count `c`.
139    pub fn comparison_count(&self) -> i64 {
140        if self.matrix.len() < 2 {
141            0
142        } else {
143            self.matrix[0][1] + self.matrix[1][0]
144        }
145    }
146}
147
148impl Problem for MaximumLikelihoodRanking {
149    const NAME: &'static str = "MaximumLikelihoodRanking";
150    type Solution = Vec<usize>;
151    type Value = Min<i64>;
152
153    crate::problem_parameters![("num_items", num_items),];
154
155    fn variant() -> Vec<(&'static str, &'static str)> {
156        crate::variant_params![]
157    }
158
159    fn evaluate(
160        &self,
161        config: &Self::Solution,
162    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
163        Ok({
164            let n = self.num_items();
165
166            // Validate config length
167            if config.len() != n {
168                return Err(crate::traits::EvaluationError::InvalidConfiguration(
169                    "ranking length does not match the number of alternatives".into(),
170                ));
171            }
172
173            if config.iter().any(|&rank| rank >= n) {
174                return Err(crate::traits::EvaluationError::InvalidConfiguration(
175                    "ranking contains an out-of-range position".into(),
176                ));
177            }
178
179            // Validate permutation: all values must be distinct and in 0..n
180            let mut seen = vec![false; n];
181            for &rank in config {
182                if rank >= n || seen[rank] {
183                    return Ok(Min(None));
184                }
185                seen[rank] = true;
186            }
187
188            // config[item] = rank position of item
189            // Disagreement cost: for all pairs of items (a, b) where a is
190            // ranked AFTER b (config[a] > config[b]), add matrix[a][b].
191            let mut cost: i64 = 0;
192            for a in 0..n {
193                for b in 0..n {
194                    if a != b && config[a] > config[b] {
195                        cost = cost.checked_add(self.matrix[a][b]).ok_or_else(|| {
196                            crate::traits::EvaluationError::IntegerOverflow(
197                                "summing ranking disagreement costs".into(),
198                            )
199                        })?;
200                    }
201                }
202            }
203
204            Min(Some(cost))
205        })
206    }
207}
208
209impl crate::solvers::BruteForceProblem for MaximumLikelihoodRanking {
210    fn dimensions(&self) -> Vec<usize> {
211        let n = self.num_items();
212        vec![n; n]
213    }
214}
215
216crate::declare_variants! {
217    default MaximumLikelihoodRanking => "num_items * num_items * 2^num_items",
218}
219
220crate::register_brute_force! {
221    MaximumLikelihoodRanking,
222}
223
224#[cfg(feature = "example-db")]
225pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
226    // 4 items with comparison matrix.
227    // Optimal ranking: [0, 1, 2, 3] (identity) gives cost 7.
228    // Let's verify: items ranked in order 0,1,2,3.
229    // Disagreement = sum over (a,b) where config[a] > config[b] of matrix[a][b]
230    // = matrix[1][0] + matrix[2][0] + matrix[2][1] + matrix[3][0] + matrix[3][1] + matrix[3][2]
231    // = 1 + 2 + 1 + 0 + 2 + 1 = 7
232    let matrix = vec![
233        vec![0, 4, 3, 5],
234        vec![1, 0, 4, 3],
235        vec![2, 1, 0, 4],
236        vec![0, 2, 1, 0],
237    ];
238    vec![crate::example_db::specs::ModelExampleSpec {
239        id: "maximum_likelihood_ranking",
240        instance: Box::new(MaximumLikelihoodRanking::new(matrix)),
241        optimal_config: serde_json::json!(vec![0, 1, 2, 3]),
242        optimal_value: serde_json::json!(7),
243    }]
244}
245
246#[cfg(test)]
247#[path = "../../unit_tests/models/misc/maximum_likelihood_ranking.rs"]
248mod tests;
problemreductions/models/misc/maximum_likelihood_ranking.rs

problemreductions/models/misc/
maximum_likelihood_ranking.rs
