Title: A note on xQx as a modelling and solution framework for the Linear Ordering Problem

Authors: Mark Lewis, Bahram Alidaee, Fred Glover, Gary Kochenberger

Addresses: Craig School of Business, Missouri Western State University, 4525 Downs Dr., Saint Joseph, MO, 64507, USA. ' School of Business, Holman Hall, University of Mississippi, University, MS, 38677, USA. ' Leeds School of Business and Department of Electrical and Computer Engineering, University of Colorado, Boulder, CO, 80309, USA. ' School of Business, University of Colorado, 1250 14th St., Denver, CO, 80202, USA

Abstract: This paper expands the list of 0-1 problems that can be effectively modelled and solved as Unconstrained Quadratic Binary Programs (UQPs). UQP has been presented as a general-purpose modelling approach with application to a broad range of problem classes (Kochenberger et al., 2004). In this paper, we demonstrate that the Linear Ordering Problem (LOP) can be easily recast so that it can be treated as a UQP problem, and that large instances of the LOP can be effectively handled within this framework. Computational results are given demonstrating the viability and attractiveness of this approach.

Keywords: linear ordering; integer programming; metaheuristics; unconstrained quadratic binary programs; modelling.

DOI: 10.1504/IJOR.2009.025005

International Journal of Operational Research, 2009 Vol.5 No.2, pp.152 - 162

Published online: 06 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article