ВЕТВЕЙ И ГРАНИЦ МЕТОД

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

В. А. Трубин.