Revised Linear Ordering Problem

A linear ordering problem (LOP) extension is presented and analyzed in this paper. LOP aims to maximize the weights in the upper triangle by simultaneously permuting rows and columns of a given weight matrix. We propose the weighted linear ordering problem (wLOP), which includes individual node weights. To begin with, we argue that the optimal order obtained by the wLOP can be a practical alternative to the optimal solution obtained by the LOP in several applications. Additionally, we show that the wLOP constitutes a generalization of the well-known Single Row Facility Layout Problem. We present an Integer Linear Programming formulation and a Variable Neighborhood Search to solve the wLOP. In our computational study, we also provide a benchmark library and evaluate the efficiency of our exact and heuristic approaches on the proposed instances

Keywords:

Integer linear programming , Variable neighborhood search , Ordering problem.