A note on xQx as a modelling and solution framework for the Linear Ordering Problem. (7th May 2009)

• Record Type: Journal Article
• Authors: Lewis, Mark; Alidaee, Bahram; Glover, Fred; Kochenberger, Gary
• Is Part Of: International journal of operational research. Volume 5:Number 2(2009)
• Page Start: 152
• Page End: 162
• Publication Date: 2009-05-07
• Subjects: linear ordering -- integer programming -- metaheuristics -- unconstrained quadratic binary programs -- modelling; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

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.