Ordering problems are a special class of combinatorial optimization problems, where weights are assigned to each ordering of n objects and the aim is to find an ordering of maximum weight. Even for the simplest case of a linear cost function, ordering problems are known to be NP-hard, i.e. it is extremely unlikely that there exists an efficient (polynomial-time) algorithm for solving ordering problems to optimality. Ordering problems arise in a large number of applications in such diverse fields as economics, business studies, social choice theory, sociology, archaeology, mathematical psychology, very-large-scale integration and flexible manufacturing systems design, scheduling, graph drawing and computational biology. In this thesis we use semidefinite optimization for solving ordering problems with up to 100 objects to provable optimality—despite their theoretical difficulty. We present a systematic investigation of semidefinite optimization based relaxations extending and improving existing exact approaches to ordering problems. We consider problems where the cost function is either linear or quadratic in the relative positions of pairs of objects. That includes well-established combinatorial optimization problems like the Linear Ordering Problem, the minimum Linear Arrangement Problem, the Single Row Facility Layout Problem, the weighted Betweenness Problem, the Quadratic Ordering Problem and Multi-level Crossing Minimization. We provide a theoretical and practical comparison of existing exact approaches based on linear, quadratic or semidefinite relaxations. Up to now there existed quite diverse exact approaches to the various ordering problems. A main goal of this thesis is to highlight their connections and to present a unifying approach by showing that the proposed semidefinite model can be successfully applied to all kinds of ordering problems. We accomplish a polyhedral study of the various ordering polytopes in small dimensions that helps us to evaluate and further improve the suggested semidefinite relaxations. We also deduce several theoretical results showcasing the polyhedral advantages of the semidefinite approach compared to Branch-and-Cut algorithms based on linear and quadratic relaxations. Additionally we introduce a new drawing paradigm for layered graphs requiring (near-)optimal solutions of an ordering problem with quadratic cost function called Multi-level Verticality Optimization. In this new drawing paradigm we are able to describe the structure of graphs more compactly and therefore obtain (well-)readable drawings of graphs too large for other available methods. We propose several heuristic and exact approaches to solve Multi-level Verticality Optimization problems and design a drawing algorithm to illustrate the (near-)optimal solutions. For tackling ordering problems of challenging size, we construct an algorithm that uses a method from nonsmooth optimization to approximately solve the proposed semidefinite relaxations and applies a rounding scheme to the approximate solutions to obtain (near-)optimal orderings. We show the efficiency of our algorithm by providing extensive computational results for a large variety of problem classes, solving many instances that have been considered in the literature for years to optimality for the first time. While the algorithm provides improved bounds for several classes of difficult instances with a linear cost function, it is clearly the method of choice for instances with quadratic cost structure (except for some very sparse instances).
Citation
PhD Thesis, Alpen-Adria-Universitaet Klagenfurt, 2012