Метод ветвей и границ теория. Задача коммивояжера - метод ветвей и границ

Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.

Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам полезными для нахождения оптимального решения.

Идея метода ветвей и границ состоит в следующем: пусть решена ослабленная задача без ограничения целочисленности, и - целочисленная переменная, значение которой в оптимальном плане является дробным. Тогда интервал

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

или
, или

Введение этих условий в задачу порождает две несвязанные между собой задачи с одной и той же целевой функцией, но непересекающимися областями допустимых значений переменных. В этом случае говорят, что задача разветвляется.

Очевидно, что возможен один из следующих четырех случаев.

Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.

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

Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Для определенности здесь и далее полагаем, что решается задача о максимуме целевой функции. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и вместе со значением целевой функции на нем дает искомое решение.

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

Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и производим ветвление на две новые задачи, разбивая область изменения этой переменной на две, ограниченные целыми числами справа и слева соответственно.

Таким образом, процесс построения все новых и новых задач может быть представлен на рисунке в виде ветвистого дерева, с вершиной, обозначенной «задача 1», и отходящими от этой вершины ветвями. Такая последовательность действий при нахождении оптимального решения задачи целочисленного программирования нашла свое отражение в названии этого метода.

Исходная вершина отвечает оптимальному плану исходной задачи 1, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам новых задач, построенных для новых ограничений по одной из переменных, имеющих в оптимальном плане задачи 1 значение в виде дробного числа.

Каждая из вершин имеет свои ответвления, при этом на каждом шаге выбирается та вершина, для которой значение целевой функции будет наибольшим.

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

Пример . Найти методом ветвей и границ решение задачи целочисленного программирования

Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.

Оптимальный план задачи 1 линейного программирования

при
.

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

Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1  и x 1 = 10 , и разобьем заданную задачу на две новые задачи.

Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.

Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:

при
.

Таким образом, в результате одного ветвления задачи было найдено ее оптимальное решение.

Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.

Алгоритм решения:

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X 0 . Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и

Если же среди компонент плана X 0 имеются дробные числа, то X 0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X 0) F(X) для всякого последующего плана X.

Предполагая, что найденный оптимальный план X 0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X 0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:

Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:

1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.

Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:

1. Находят решение задачи линейного программирования (1)-(3).
2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.

целочисленный программирование задача коммивояжер ранец

Общее описание

Общая идея метода может быть описана на примере поиска минимума функции на множестве допустимых значений переменной . Функция и переменная могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура ветвления состоит в разбиении множества допустимых значений переменной на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево , называемое деревом поиска или деревом ветвей и границ . Узлами этого дерева являются построенные подобласти (подмножества множества значений переменной ).

Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной .

В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева ). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

Применение

Метод используется для решения некоторых NP-полных задач, таких как:

См. также

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое "Метод ветвей и границ" в других словарях:

метод ветвей и границ - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва] Тематики электротехника, основные понятия EN branch and bound method … Справочник технического переводчика

метод - метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди … Словарь-справочник терминов нормативно-технической документации

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия

У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия

Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной. Задача о ранце (рюкзаке) (англ. … Википедия

Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия

Книги

Разработка программного средства для поиска оптимального портфеля оптовых закупок торгового предприятия , А. В. Мищенко. В рамках настоящей работы разработано программное средство для решения задачи поиска оптимального портфеля оптовых закупок предприятия розничной торговли. При этом использован метод ветвей и…

Впервые метод ветвей и границ был предложен в 1960 г. в работе Лэнд и Дойг применительно к задаче целочисленного линейного программирования. Однако эта работа не оказала заметного непосредственного влияния на развитие дискретного программирования. Фактически «второе рождение» метода ветвей и границ связано с работой Литтла, Мурти, Суини и Кэрел , посвященной задаче коммивояжера; в этой же работе было впервые предложено и общепринятое теперь название метода «метод ветвей и границ». Начиная с этого момента появляется весьма большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех (да еще применительно к «классически трудной» задаче о коммивояжере) объясняется тем, что Литтл, Мурти, Суини и Кэрел первыми обратили внимание на широту возможностей метода ветвей и границ, отметили важность использования специфики задачи и сами весьма удачно этой спецификой воспользовались.

В § 1 настоящей главы излагается общая идея метода ветвей и границ; в § 2 - алгоритм Лэнд и Дойг для задачи целочисленного линейного программирования, в § 3 - метод Литтла и др. авторов для задачи коммивояжера.

§ 1. Идея метода ветвей и границ

1.1. Рассмотрим задачу дискретного программирования в следующей общей форме.

Минимизировать

при условии

Здесь G - некоторое конечное множество.

1.2. В основе метода ветвей и границ лежат следующие построения, позволяющие в ряде случаев существенно уменьшить объем перебора.

I. Вычисление нижней границы (оценки).

Часто удается найти нижнюю границу (оценку) целевой функции на множестве планов (или на некотором его подмножестве т. е. такое число что для имеет место

(соответственно для имеет место Разбиение на подмножества (ветвление). Реализация метода связана с постепенным разбиением множества планов на дерево подмножеств (ветвлением). Ветвление происходит по следующей многошаговой схеме.

0-й шаг. Имеется множество Некоторым способом оно разбивается на конечное число (обычно не пересекающихся) подмножестве шаг Имеются множества , еще не подвергавгпиеся ветвлению. По некоторому правилу (указанному ниже) среди них выбирается множество и разбивается на конечное число подмножеств:

Еще не подвергавшиеся разбиению множества

заново обозначаются через

Несколько шагов такого процесса последовательного разбиения схематически изображены на рис. 10.1.1.

III. Пересчет оценок. Если множество то, очевидно,

Поэтому, разбивая в процессе решения некоторое множество на подмножества

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

IV. Вычисление планов. Для конкретных задач могут быть указаны различные способы нахождения планов в последовательно разветвляемых подмножествах. Любой такой способ существенно опирается на специфику задачи.

V. Признак оптимальности. Пусть

и план X принадлежит некоторому подмножеству Если при этом

то X - оптимальный план задачи (1.1) - (1.2).

Доказательство непосредственно следует из определения оценки.

Обычно этот признак применяется на некотором этапе ветвления (т. е., говоря формально, при ; см. п. II).

VI. Оценка точности приближенного решения. Пусть

Если X - некоторый план исходной задачи (т. е. ), то

Доказательство и здесь сразу следует из определения оценки.

Очевидно, что если разность невелика (т. е. не превышает некоторого выбранного для данной задачи числа), то X можно принять за приближенное решение, за оценку точности приближения.

1.3. Изложим формальную схему метода ветвей и границ.

0-й шаг. Вычисляем оценку . Если при этом удается найти такой план X, что

то X - оптимальный план.

Если оптимальный план не найден, то по некоторому способу разбиваем множество на конечное число подмножеств

и переходим к шагу.

1-й шаг. Вычисляем оценки Если при этом удается найти такой план X, что для некоторого и

то X - оптимальный план.

Если же оптимальный план не найден, то выбираем «наиболее перспективное» для дальнейшего разбиения множество по следующему правилу:

Разбиваем множество на несколько (обычно не пересекающихся) подмножеств.

Начало развитию подхода, получившего название метод ветвей и границ, положила работа Ленд и Дойг (1960). Это, скорее, даже не метод, а концепция или процедурная оболочка, на основе которой стали разрабатывать алгоритмы решения целочисленных задач различной природы. Ценность предложенной идеи стала особенно заметна после появления первого точного алгоритма решения задачи коммивояжера, построенного по схеме ветвей и границ (Литтл с соавторами, 1963). Метод можно применять как к полностью, так и частично целочисленным задачам.

Суть идеи схожа с известной шуткой о ловле льва в пустыне: делим пустыню пополам; если льва нет в первой половине, ищем во второй, которую делим пополам и т. д. В отличии от льва оптимум не перемещается, и в этом смысле наша задача легче.

Метод заключается в построении дерева задач, корнем которого является исходная задача, возможно без условия целочисленности (НЗ). Нижележащие задачи порождаются вышележащими так, что их допустимые множества (ДМ) являются непересекающимися подмножествами ДМ вышележащей задачи. Рост дерева происходит за счет перспективных ветвей. Перспективность определяется по оценке критерия терминальной задачи ветвиV ирекорду Z. ОценкаV – это значение критерия, заведомо не хуже оптимального, аZ – достигнутое в процессе решения значение критерия исходной задачи (в качестве начального может приниматься значение, заведомо хуже оптимального). Значит, задача будет порождающей только при условии, что ее оценка лучше рекорда. При этом уровень, на котором находится задача, не имеет значения.

Рассмотрим метод применительно к линейной целочисленной задаче. Хотя нет каких-либо ограничений на число задач, непосредственно порождаемых перспективной, в алгоритмах, как правило, используется разбиение на две задачи, то есть строится бинарное дерево (рис. 7.5). При этом для целочисленных множеств выполняются соотношения

Очевидно, что если, например,V 22 окажется хуже рекорда илиD 22 =, правая ветвь обрывается (говорят также, что она прозондирована). Если же оценкаV 22 будет лучше Z , производится ветвление: множествоD 22 разбивается на 2 подмножества. Решение завершится, когда все ветви будут прозондированы.

Вид оценки зависит от направленности критерия: при максимизации используется верхняя оценка, при минимизации – нижняя. Последующее изложение метода будет относиться к задаче на максимум.

Для алгоритмической реализации схемы ветвей и границ необходимо решить два основополагающих вопроса:

Каким образом разбивать перспективное множество на подмножества;

Как определять верхнюю оценку критерия на рассматриваемом множестве.

Ответы на них зависят от типа задачи (частично или полностью целочисленная, имеет особые свойства или нет, с булевыми или не булевыми переменными). Ниже рассматривается общий случай.

Пусть известен диапазон возможных значений j -й переменной

0  х j  d j ,

которая в непрерывном оптимальном решении оказалась нецелочисленной и равной x j * . Тогда целочисленное значение этой переменной может достигаться либо в интервале 0  х j 
,либо в интервале
+1 х j  d j , где
- целая часть (рис. 7.6).

Это соответствует разбиению непрерывного множестваD н на два непересекающихся подмножества D 1 н и D 2 н , объединение которых не равно D н . В то же время такое разбиение целочисленного множества удовлетворяет соотношениям (7.9). При этом целочисленные множества, как исходное, так и порожденные, включены в соответствующие непрерывные множества. Следовательно, поиск целочисленного решения на непрерывном множестве даст тот же результат, что и на целочисленном. Легко увидеть, что приведенное выделение подинтервалов по одной переменной приводит к разбиению исходного множества на два подмножества при любом числе переменных.

Теперь перейдем ко второму вопросу. Так как целочисленное множество является подмножеством соответствующего непрерывного, оптимальное значение критерия на непрерывном множестве всегда будет не меньше, чем на целочисленном. Поэтому в качестве верхней оценки V можно брать оптимальное значение критерия L * непрерывной задачи.

Выбор начального значения рекорда зависит от ситуации:

если известно какое-либо целочисленное значение, то рекорд принимается равным критерию в этом решении;

при положительности всех коэффициентов критерия можно взять нулевое значение рекорда;

в иных случаях за начальное значение рекорда берется –М , где М- максимально представимое в компьютере число.

По ходу разбиения формируются порождаемые задачи, которые помещаются в список задач. Первоначальный список содержит только одну задачу – исходную задачу без условий целочисленности. И в последующем список будет содержать только непрерывные задачи.

Таким образом, базовый алгоритм, реализующий метод ветвей и границ, включает следующие шаги.

Приведенный алгоритм является базовым, так как не включает однозначных правил выбора задачи из списка и ветвящей переменной. Для частично целочисленных задач при выборе переменной для ветвления исключаются непрерывные переменные.

Пример 7.3 . Применим алгоритм ветвей и границ к задаче

L= 9x 1 + 5x 2  max;

3x 1 - 6x 2  1;

5x 1 +2x 2  28;

 x j  0 , целые.

Отбрасывая условие цедочисленности, получаем непрерывную задачу, которую помещаем в список задач. Так как коэффициенты критерия положительны, начальное значение рекорда принимаем равным нулю. Берем из списка единственную задачу и решаем ее. Получаем оптимальное решение в вершине А (рис. 7.7):x 1 * =4,72; x 2 * =2,19 . Ветвление производим по переменнойx 1 . Добавляя к решенной задаче ограничение x 1 4, образуем задачу 2, а добавление x 1 5 дает задачу 3. Допустимые множества новых задач покзаны на рис. 7.7. Эти задачи помещаем в список задач. Решение задачи 2 достигается в точке В, а задачи 3 – в С. Весь ход решения исходной задачи представлен в виде дерева решений на рис. 7.10. Порядок решения задач из списка отражает счетчик итераций k . На 3-й итерации (задача 4) получено целочисленное решение со значением критерия 41 (точка D нарис. 7.8). Поэтому изменяется рекорд: Z =41.Задача 6 имеет нецелочисленное решение (вершина Е на рис. 7.9), задача 8 – целочисленное решение в точкеF. В результате после 7-й итерации рекорд становится равным 50.

Остальные задачи не имеют допустимых решений, то есть список задач исчерпывается и, таким образом, констатируем получение оптимального решения исходной задачи, равное решению непрерывной задачи 8.

Из приведенного дерева решений видно, что число задач в списке могло быть меньше при другом порядке решения задач. Действительно, если бы сначала были решены задачи правой ветви с рекордом Z= 50, то после решения задачи 2 не произошло бы ветвления, так как верхняя оценка оказалась бы ниже рекорда (V=L * =45,17<50).

Естественно возникает вопрос: а как на числе задач и дереве решений может отразиться выбор другой переменной для ветвления? Так, в нашем примере если после 1-й итерации произвести ветвление по переменнойx 2 , то получим дерево, показанное на рис. 7.11. Оно содержит на 2 задачи больше, чем на рис. 7.10. Конечно, оно может быть также другим при ином порядке решения задач.

Таким образом, число решаемых задач существенно зависит от выбора задачи из списка и переменной для ветвления.

Из алгоритма и приведенного примера следует, что ветвь обрывается по одной из трех причин:

неразрешимость задачи;

задача имеет целочисленное решение;

верхняя оценка не больше рекорда.

Теперь сделаем ряд замечаний относительно метода ветвей и границ. Как уже отмечалось, в базовом алгоритме не оговариваются правила выбора задачи и переменной. В большинстве программных реализаций метода используются правила, основанные на эвристических оценках перспективности задач и переменных. В некоторых пакетах, например, "ЛП в АСУ" предлагается несколько вариантов управления процессом решения: от автоматического до ручного, в котором пользователь может сам делать выбор как задачи, так и переменной. Кроме того, алгоритмы, основанные на методе ветвей и границ, могут существенно отличаться в связи с учетом особенностей класса задач. Например, для задачи коммивояжера, определение оценки значительно упрощено (не требуется решать непрерывную линейную задачу).

Метода ветвей и границ имеет преимущества в сравнении с методом отсечений:

накопление ошибок менее значительное, так как решение идет по разным ветвям;

при принудительной остановке процесса решения высока вероятность получения целочисленного результата, но без установления его оптимальности;

при решении непрерывных задач размеры симплекс-таблиц не увеличиваются.

Недостатки метода ветвей и границ:

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

Отсутствие признака оптимальности. Оптимальное решение может быть получено задолго до останова алгоритма, но обнаружить это в общем случае нельзя. Оптимальность устанавливается только по исчерпании списка задач.

Очевидно, что эффективность метода повышается с уменьшением диапазонов значений переменных и числа нецелых переменных в решении первой непрерывной задачи.