Article ID: | iaor20101970 |
Volume: | 22 |
Issue: | 1 |
Start Page Number: | 168 |
End Page Number: | 177 |
Publication Date: | Dec 2010 |
Journal: | INFORMS Journal on Computing |
Authors: | Buchheim Christoph, Wiegele Angelika, Zheng Lanbo |
Keywords: | programming: quadratic |
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.