This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Buchheim, C. Articles by Zheng, L. Search for Related Content

Exact Algorithms for the Quadratic Linear Ordering Problem

Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 53113 Bonn, Germany
Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, 9020 Klagenfurt, Austria
NICTA, The University of New South Wales, Sydney, New South Wales 2052, Australia
buchheim{at}or.uni-bonn.de
angelika.wiegele{at}uni-klu.ac.at
lanbo.zheng{at}nicta.com.au

The quadratic linear ordering problem naturally generalizes various optimization problems such as bipartite crossing minimization or the betweenness problem, which includes linear arrangement. These problems have important applications, e.g., in automatic graph drawing and computational biology. We present a new polyhedral approach to the quadratic linear ordering problem that is based on a linearization of the quadratic objective function.

Our main result is a reformulation of the 3-dicycle inequalities using quadratic terms. After linearization, the resulting constraints are shown to be face-inducing for the polytope corresponding to the unconstrained quadratic problem. We use this result both within a branch-and-cut algorithm and within a branch-and-bound algorithm based on semidefinite programming. Experimental results for bipartite crossing minimization show that this approach clearly outperforms other methods.

Key words: quadratic optimization; linear ordering; crossing minimization
History: received January 2008; revised December 2008; accepted January 2009.