A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments |
| |
Authors: | Irène Charon |
| |
Institution: | École nationale supérieure des télécommunications, 46, rue Barrault, 75634 Paris cedex 13, France |
| |
Abstract: | The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater's problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree. |
| |
Keywords: | Linear ordering problem Slater's problem Kemeny's problem Median order Tournaments Branch and bound Lagrangean relaxation Noising methods |
本文献已被 ScienceDirect 等数据库收录! |
|