The Weighted Linear Ordering Problem

In this work, we introduce and analyze an extension of the Linear Ordering Problem ( LOP) . The LOP aims to find a simultaneous permutation of rows and columns of a given weight matrix such that the sum of the weights in the upper triangle is maximized. We propose the weighted Linear Ordering Problem ( wLOP) that additionally considers individual node weights.

First, we argue that in several applications of the LOP the optimal ordering obtained by the wLOP is a worthwhile alternative to the optimal solution of the LOP. Additionally, we show that the wLOP constitutes a generalization of the well-known Single Row Facility Layout Problem.

We introduce an Integer Linear Programming formulation as well as a Variable Neighborhood Search for solving the wLOP. Finally, we provide a benchmark library and examine the efficiency of our exact and heuristic approaches on the proposed instances in a computational study.