Groupe d’études et de recherche en analyse des décisions

Semidefinite Approaches to Ordering Problems

Philipp Hungerländer Alpen-Adria-Universität Klagenfurt, Autriche

Combinatorial optimization and semidefinite programming have been two very active research areas during the past two decades. Combinatorial optimization is concerned with finding (near-)optimal solutions for many different real-world problems by using heuristic, approximation and exact algorithms. Semidefinite programming builds the basis for some of the most advanced approximation results in computer science and is applied to practical problems in control theory, engineering and combinatorial optimization.

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-complete. They arise in a large number of applications in such diverse fields as economics, VLSI and FMS design, scheduling, graph drawing and computational biology.

In this talk we suggest to use semidefinite optimization for solving reasonably sized instances of ordering problems to provable optimality|despite their theoretical complexity class. 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.

Up to now there existed quite diverse exact approaches to the various ordering problems. A main goal of this talk 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 give some theoretical results that showcase the polyhedral advantages of the semidefinite approach compared to ILP Branch-and-Cut algorithms. For practically tackling ordering problems, 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 the algorithm 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.