Том 8, серия 2, номер 2, 2001 г., Стр. 73-91
УДК 519.854.64
И. Шарон, О. Юдри
Метод ветвей и границ для решения задачи о линейном порядке на взвешенных турнирах
Аннотация:
В турнире, дугам которого приписаны неотрицательные веса, требуется найти множество дуг с минимальным суммарным весом, смена ориентации которых преобразует исходный турнир в транзитивный. Для решения этой задачи предлагается новый вариант метода ветвей и границ. При вычислении нижних оценок целевой функции используется техника лагранжевых релаксаций. Верхние оценки находятся с помощью метода шума. Приводятся результаты численного эксперимента на турнирах, содержащих не более 100 вершин.
Табл. 1, ил. 7, библиогр. 32.
Шарон И. 1
Юдри О. 1
1. National Center of Scientific Research ENST,
46, rue Barrault,
75634 Paris, cedex 13, France
е-mail: hudry@infres.enst.fr
Статья поступила 26 июня 2000 г.
Исправленный вариант — 16 февраля 2001 г.
