Median linear orders: Heuristics and a branch and bound algorithm (Q582183)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Median linear orders: Heuristics and a branch and bound algorithm |
scientific article |
Statements
Median linear orders: Heuristics and a branch and bound algorithm (English)
0 references
1989
0 references
The first part of this paper illustrates the relationship between median linear orders and the so-called minimum arc set problem. In the second part a heuristic is studied to solve the minimum feedback arc set problem for non-weighed tournaments, which is then extended to the general case (weighed tournaments). In the last part, a branch and bound (b \& b) method is designed to get all median linear orders associated with a profile of linear orders. Among the advantages of the b \& b method are: (1) whereas most methods are only able to compute just one median linear order, b \& b computes all of them; (2) b \& b always provides exact integer solutions; (3) the algorithm for the b \& b method can be easily set up on any microcomputer for reasonable sized data.
0 references
heuristics
0 references
multicriteria decision aid
0 references
median linear orders
0 references
minimum arc set problem
0 references
minimum feedback arc set problem
0 references
non-weighed tournaments
0 references
branch and bound
0 references