Optimization Online


Exact Algorithms for the Quadratic Linear Ordering Problem

Christoph Buchheim (buchheim***at***informatik.uni-koeln.de)
Angelika Wiegele (angelika.wiegele***at***uni-klu.ac.at)
Lanbo Zheng (lzheng***at***it.usyd.edu.au)

Abstract: 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 in, e.g., 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, the resulting constraints are shown to be face-inducing for the polytope corresponding to the unconstrained quadratic problem. We exploit this result both within a branch-and-cut algorithm and within an SDP-based branch-and-bound algorithm. Experimental results for bipartite crossing minimization show that this approach clearly outperforms other methods.

Keywords: quadratic optimization, linear ordering, crossing minimization

Category 1: Combinatorial Optimization

Citation: Technical report (zaik2007-560), Zentrum f. Angewandte Informatik Köln.


Entry Submitted: 11/21/2007
Entry Accepted: 11/21/2007
Entry Last Modified: 09/14/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society