Exact Algorithms for the Quadratic Linear Ordering Problem - Kölner UniversitätsPublikationsServer

Buchheim, Christoph ORCID: 0000-0001-9974-404X, Wiegele, Angelika ORCID: 0000-0003-1670-7951 and Zheng, Lanbo (2007). Exact Algorithms for the Quadratic Linear Ordering Problem. INFORMS Journal on Computing, 22 (1). pp. 168-177. Informs. Open Access

Preview

PDF
zaik2007-560.pdf
Download (169kB) | Preview

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.

Item Type:

Journal Article

Creators:

Creators	Email	ORCID	ORCID Put Code
Buchheim, Christoph	UNSPECIFIED	orcid.org/0000-0001-9974-404X	UNSPECIFIED
Wiegele, Angelika	UNSPECIFIED	orcid.org/0000-0003-1670-7951	UNSPECIFIED
Zheng, Lanbo	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED