corankco.algorithms.exact package

Submodules

corankco.algorithms.exact.exactalgorithm module

Module that contains the class ExactAlgorithm, which consists in choosing Cplex or PuLP version of the exact algorithm according to the possibility to import cplex.

class corankco.algorithms.exact.exactalgorithm.ExactAlgorithm(optimize=True)

Bases: ExactAlgorithmBase

This class provides a wrapper for exact ranking algorithms. It intelligently selects an appropriate exact algorithm depending on the availability of the Cplex library. If Cplex is not installed, the class defaults to a free solver.

The complexity of this algorithm is exponential. In practical use cases, it is expected to execute within a few seconds for ranking tasks involving fewer than 80 elements. For larger sets of elements, the performance will be significantly influenced by specific characteristics of the input rankings.

Particularly, if the size of the largest strongly connected component (as described in the research paper “Efficient, robust, and effective rank aggregation for massive biological datasets” (https://www.researchgate.net/publication/352277711_Efficient_robust_and_effective_rank_aggregation_for_massive_biological_datasets)) exceeds 100, the algorithm may not complete in a reasonable timeframe or may require excessive memory. This information can be determined using ParConsPartition class.

compute_consensus_rankings(dataset: Dataset, scoring_scheme: ScoringScheme, return_at_most_one_ranking: bool = True, bench_mode: bool = False) → Consensus
Parameters:

  • dataset (Dataset (class Dataset in package 'datasets')) – A dataset containing the rankings to aggregate

  • scoring_scheme (ScoringScheme (class ScoringScheme in package 'distances')) – The penalty vectors to consider

  • return_at_most_one_ranking (bool) – the algorithm should not return more than one ranking

  • bench_mode (bool) – is bench mode activated. If False, the algorithm may return more information

:return one or more rankings if the underlying algorithm can find several equivalent consensus rankings If the algorithm is not able to provide multiple consensus, or if return_at_most_one_ranking is True then, it should return a list made of the only / the first consensus found. In all scenario, the algorithm returns a list of consensus rankings :raise ScoringSchemeNotHandledException when the algorithm cannot compute the consensus because the implementation of the algorithm does not fit with the scoring scheme

get_full_name() → str
Returns:

The name of the algorithm, depends on which has been used between Cplex and PULP

is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ScoringScheme)

Check if the scoring scheme is relevant when the rankings are incomplete.

Parameters:

scoring_scheme (ScoringScheme) – The scoring scheme to be checked.

Returns:

True as ExactAlgorithmCplex can handle any ScoringScheme

Return type:

bool

corankco.algorithms.exact.exactalgorithmbase module

Module containing an abstract class for Exact Algorithm.

class corankco.algorithms.exact.exactalgorithmbase.ExactAlgorithmBase(optimize: bool = True)

Bases: ABC, RankAggAlgorithm

An abstract base class for exact algorithms. This class outlines the interface that all exact algorithms must implement.

abstract compute_consensus_rankings(dataset: Dataset, scoring_scheme: ScoringScheme, return_at_most_one_ranking=True, bench_mode=False) → Consensus

Abstract method to compute consensus rankings.

Parameters:

  • dataset – A dataset containing the rankings to aggregate.

  • scoring_scheme – The penalty vectors to consider.

  • return_at_most_one_ranking – The algorithm should not return more than one ranking.

  • bench_mode – Is bench mode activated. If False, the algorithm may return more information.

Returns:

One or more consensus rankings.

abstract get_full_name() → str

Abstract method to get the full name of the algorithm.

Returns:

The full name of the algorithm as a string.

abstract is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ScoringScheme) → bool

Abstract method to check if the scoring scheme is relevant when rankings are incomplete.

Parameters:

scoring_scheme – The scoring scheme to check.

Returns:

True if the scoring scheme is relevant, False otherwise.

exception corankco.algorithms.exact.exactalgorithmbase.IncompatibleArgumentsException

Bases: Exception

Custom exception, to warn the user that the “optimize” parameter can not be True if the user wants all the optimal consensuses.

corankco.algorithms.exact.exactalgorithmcplex module

Module that contains a class as an Exact Algorithm, ILP based, for Kemeny-Young rank aggregation. This algorithm uses Cplex.

class corankco.algorithms.exact.exactalgorithmcplex.ExactAlgorithmCplex(optimize=True)

Bases: ExactAlgorithmBase, PairwiseBasedAlgorithm

A class to perform exact optimization on the rank aggregation problem using CPLEX linear programming. More information can be found in P.Andrieu, S.Cohen-Boulakia, M.Couceiro, A.Denise, A.Pierrot. A Unifying Rank Aggregation Model to Suitably and Efficiently Aggregate Any Kind of Rankings. https://dx.doi.org/10.2139/ssrn.4353494 Note: This implementation uses CPLEX, which is proprietary software. Users must download and install CPLEX separately from the IBM website. While CPLEX is not open source, there is a free version available for academic use. More information can be found at: https://www.ibm.com/products/ilog-cplex-optimization-studio

Variables:

_PRECISION_THRESHOLD – float representing the precision threshold used for floating point comparison

compute_consensus_rankings(dataset: Dataset, scoring_scheme: ScoringScheme, return_at_most_one_ranking=True, bench_mode=False) → Consensus
Parameters:

  • dataset (Dataset (class Dataset in package 'datasets')) – A dataset containing the rankings to aggregate

  • scoring_scheme (ScoringScheme (class ScoringScheme in package 'distances')) – The penalty vectors to consider

  • return_at_most_one_ranking (bool) – the algorithm should not return more than one ranking

  • bench_mode (bool) – is bench mode activated. If False, the algorithm may return more information

:return one or more rankings if the underlying algorithm can find several equivalent consensus rankings If the algorithm is not able to provide multiple consensus, or if return_at_most_one_ranking is True then, it should return a list made of the only / the first consensus found. In all scenario, the algorithm returns a list of consensus rankings :raise ScoringSchemeNotHandledException when the algorithm cannot compute the consensus because the implementation of the algorithm does not fit with the scoring scheme

get_full_name() → str

Return the full name of the algorithm.

Returns:

The string ‘Exact algorithm ILP Cplex’.

Return type:

str

is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ScoringScheme) → bool

Check if the scoring scheme is relevant when the rankings are incomplete.

Parameters:

scoring_scheme (ScoringScheme) – The scoring scheme to be checked.

Returns:

True as ExactAlgorithmCplex can handle any ScoringScheme

Return type:

bool

corankco.algorithms.exact.exactalgorithmcplexforpaperoptim1 module

Module for a version of the Exact Algorithm that uses only one optimization. Mainly to reproduce the experiment 1 of the IJAR paper.

class corankco.algorithms.exact.exactalgorithmcplexforpaperoptim1.ExactAlgorithmCplexForPaperOptim1

Bases: ExactAlgorithmCplex

A class to perform exact optimization on the rank aggregation problem using CPLEX linear programming. This class was used for the experiments presented in Andrieu et al., IJAR, 2023. The objective is to consider only one of the possible optimizations: a sufficient condition to ensure that at least one optimal consensus is a ranking without ties This class only re-defines the function to get personalized contraints based on sufficient conditions.

More information can be found in the following article: Andrieu et al., IJAR, 2023.

get_full_name() → str

Return the full name of the algorithm.

Returns:

The string ‘Exact algorithm ILP Cplex’.

Return type:

str

corankco.algorithms.exact.exactalgorithmpulp module

Module for an Exact Algorithm, ILP based, using PuLP

class corankco.algorithms.exact.exactalgorithmpulp.ExactAlgorithmPulp

Bases: RankAggAlgorithm, PairwiseBasedAlgorithm

Exact algorithm using free libraries

compute_consensus_rankings(dataset: Dataset, scoring_scheme: ScoringScheme, return_at_most_one_ranking=False, bench_mode=False) → Consensus
Parameters:

  • dataset (Dataset (class Dataset in package 'datasets')) – A dataset containing the rankings to aggregate

  • scoring_scheme (ScoringScheme (class ScoringScheme in package 'distances')) – The penalty vectors to consider

  • return_at_most_one_ranking (bool) – the algorithm should not return more than one ranking

  • bench_mode (bool) – is bench mode activated. If False, the algorithm may return more information

:return one or more rankings if the underlying algorithm can find several equivalent consensus rankings If the algorithm is not able to provide multiple consensus, or if return_at_most_one_ranking is True then, it should return a list made of the only / the first consensus found. In all scenario, the algorithm returns a list of consensus rankings :raise ScoringSchemeNotHandledException when the algorithm cannot compute the consensus because the implementation of the algorithm does not fit with the scoring scheme

get_full_name() → str

Return the full name of the algorithm.

Returns:

The string ‘Exact algotrithm ILP pulp’.

Return type:

str

is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ScoringScheme) → bool

Check if the scoring scheme is relevant when the rankings are incomplete.

Parameters:

scoring_scheme (ScoringScheme) – The scoring scheme to be checked.

Returns:

True as ExactAlgorithmCplex can handle any ScoringScheme

Return type:

bool

Module contents

Module to manage the Exact Algorithm. Several versions are provided: one with Cplex, one that uses PuLP. The class Exact Algorithm chooses Cplex if Cplex can be imported. The ExactAlgorithmBase is an interface for exact algorithms.