ConcordanceTest (version 1.0.3)

LOP: Linear Ordering Problem (LOP)

Description

This function computes the solution of the Linear Ordering Problem.

Usage

LOP(mat_LOP)

Value

The function returns a list with the following elements:

1. obj_val: Optimal value of the solution of the Linear Ordering Problem, i.e., the sum of the elements above the main diagonal under the permutation rows/cols solution.

2. permutation: Solution of the Linear Ordering Problem, i.e., the rows/cols permutation.

3. permutation_matrix: Optimal permutation matrix of the Linear Ordering Problem.

Arguments

mat_LOP

Preference matrix defining the Linear Ordering Problem. A numeric square matrix for which we want to obtain the permutation of rows/columns that maximizes the sum of the elements above the main diagonal.

References

Martí, R. and Reinelt, G. The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Springer, first edition 2011.

Examples

## Square matrix
##
##  |  1    2    2  |
##  |  2    3    3  |
##  |  3    2    2  |
##
## The optimal permutation of rows/cols is (2,3,1),
## and the solution of the Linear Ordering Problem is 8.
## Te permutation matrix of the solution is
##  |  0    0    0  |
##  |  1    0    1  |
##  |  1    0    0  |

mat_LOP <- matrix(c(1,2,3,2,3,2,2,3,2), nrow=3)
LOP(mat_LOP)