INFORMS journal on computing · 2009 · 46 citations · 7 references
Natural SciencesComputer ScienceMathematicsAlgorithmsComputational BiologyOptimizationBranch And BoundCombinatorial OptimizationConvex OptimizationGraph AlgorithmsLinear ProgrammingQuadratic ProgrammingBranch-and-cutConstraintsCrossing MinimizationExact AlgorithmsObjective Function FormulationPolyhedral AnalysisPolyhedral TheorySemidefinite Programming
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.
7
Francisco Barahona, Ali Ridha Mahjoub · Mathematical Programming · 1986 · 379 citations
Edge crossings in drawings of bipartite graphs
Peter Eades, Nicholas Wormald · Algorithmica · 1994 · 290 citations
Facets of the linear ordering polytope
Martin Grötschel, Michael Jünger, Gerhard Reinelt · Mathematical Programming · 1985 · 173 citations