4.5. Вычислительная характеристика алгоритма решения ЗНП

Вычислительные возможности алгоритма, описанного в разд. 4.4 и предназначенного для решения ЗНП, представлены в табл. 3.2. Во второй и третьей графах таблицы даны числа строк и столбцов, полученные после применения упрощающих

правил. Данные во всех задачах задавались случайным образом, а стоимости брались равными единице, т. е. , для каждого столбца 7.

Таблица 3.2 (см. скан) Время вычисления при решении ЗНП

Лемке, Салкин и Шпильберг [41] предложили такие методы решения ЗНП, в которых используются дерево поиска (иного типа), а также линейные программы. Решение соответствующей задачи линейного программирования берется в качестве нижней границы в процессе поиска и, кроме того, определяет характер последующего ветвления в текущем узле дерева поиска. Подходы, базирующиеся на рассмотрении отсекающих плоскостей и подобные, в принципе, тем, которые применяются в общем -программировании [32], представлены в работах Хауза, Нелсона и Радо [35] и Белмора и Рэтлифа [9]. Сравнение этих методов и исследование их вычислительных характеристик дается в статье Кристофидеса и Кормана [19].