[Rule] MaximumLikelihoodRanking to ILP

[isPANN]

Motivation

Direct ILP formulation for MaximumLikelihoodRanking. Companion issue for #930.

Source

MaximumLikelihoodRanking

Target

ILP

Reference

Standard ILP for minimum disagreement ranking / Kemeny ranking.

Reduction Algorithm

Input: n×n comparison matrix A with a_ij + a_ji = c.

1. Binary variables x_{ij} ∈ {0, 1} for all i ≠ j (x_{ij} = 1 iff item i is ranked before item j).
2. Antisymmetry: x_{ij} + x_{ji} = 1 for all i ≠ j.
3. Transitivity: x_{ij} + x_{jk} + x_{ki} ≤ 2 for all distinct i, j, k.
4. Objective: minimize Σ_{i≠j} a_{ij} · x_{ji} (cost of placing i before j when j was preferred).

Solution extraction: Topological sort of the ordering defined by x_{ij}.

Size Overhead

Code metric	Formula
num_variables	n*(n-1)
num_constraints	n*(n-1)/2 + n*(n-1)*(n-2)

Validation Method

Closed-loop test.

Example

Source: 3 items, A = [[0,3,1],[1,0,2],[2,1,0]].
Optimal: x_{01}=1, x_{02}=1, x_{12}=1 → ranking (0,1,2), cost = 1+2+1 = 4. Min(4).

[isPANN]

Please kindly check the following items (PR #976):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.