Разделить и разрезать

Branch and cut ^[1] - это метод комбинаторной оптимизации для решения целочисленных линейных программ (ILP), то есть задач линейного программирования (LP), в которых некоторые или все неизвестные ограничены целочисленными значениями. ^[2] Разделение и вырезание включает в себя выполнение алгоритма ветвей и границ и использование плоскостей сечения, чтобы ужесточить релаксации линейного программирования. Обратите внимание, что если сокращения используются только для ужесточения начальной релаксации LP, алгоритм называется разрезанием и ветвлением.

Алгоритм [ править ]

Это описание предполагает, что ILP - это проблема максимизации .

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

На этом этапе начинается ветвление и граница алгоритма. Проблема разбита на несколько (обычно две) версии. Затем новые линейные программы решаются симплексным методом, и процесс повторяется. В процессе ветвей и границ нецелые решения LP-релаксации служат в качестве оценок сверху, а интегральные решения - в качестве оценок снизу. Узел может быть сокращен, если его верхняя граница ниже существующей нижней границы. Кроме того, при решении LP-релаксации могут быть сгенерированы дополнительные плоскости сечения, которые могут быть либо глобальными разрезами , т. Е. Действительными для всех возможных целочисленных решений, либо локальными разрезами., что означает, что им удовлетворяют все решения, удовлетворяющие боковым ограничениям из рассматриваемого в настоящее время ветвления и привязанного поддерева.

Ниже приводится краткое изложение алгоритма.

Добавить исходную ILP в список активных проблем. ${\ displaystyle L}$
Установить и ${\ displaystyle x ^ {*} = {\ text {null}}}$ ${\ displaystyle v ^ {*} = - \ infty}$
пока не пусто ${\ displaystyle L}$
1. Выбрать и удалить (удалить из очереди) проблему из ${\ displaystyle L}$
2. Решите ЛП релаксацией проблемы.
3. Если решение неосуществимо, вернитесь к 3 (пока). В противном случае обозначьте решение значком с объективным значением . ${\ displaystyle x}$ ${\ displaystyle v}$
4. Если , вернитесь к 3. ${\ displaystyle v \ leq v ^ {*}}$
5. Если целое число, установите и вернитесь к 3. ${\ displaystyle x}$ $v^{*}\leftarrow v,x^{*}\leftarrow x$
6. При желании ищите плоскости сечения, которые нарушаются . Если таковые обнаружены, добавьте их к релаксации LP и вернитесь к 3.2. $x$
7. Разделение для разделения проблемы на новые проблемы с ограниченными возможными регионами. Добавьте эти проблемы и вернитесь к 3 $L$
возвращаться $x^{*}$

Псевдокод [ править ]

В псевдокоде , подобном C ++ , это можно было бы записать:

// Псевдокод решения ветвления и отсечения ILP, предполагая, что цель должна быть максимизированаILP_solution  branch_and_cut_ILP ( IntegerLinearProgram  initial_problem )  { очередь  active_list ;  // L, выше активный_лист . Enqueue ( initial_problem );  // шаг 1 // шаг 2 ILP_solution  optim_solution ;  // это будет содержать x * выше double  best_objective  =  - std :: numeric_limits < двойной > :: бесконечность ;  // будет содержать v * выше while  ( ! active_list . empty ())  {  // шаг 3 выше LinearProgram &  curr_prob  =  active_list . dequeue ();  // шаг 3.1 do  {  // шаги 3.2–3.7 RelaxedLinearProgram и  relaxed_prob  =  LP_relax ( curr_prob );  // шаг 3.2 LP_solution  curr_relaxed_soln  =  LP_solve ( relaxed_prob );  // это x выше bool  cut_planes_found  =  false ; if  ( ! curr_relaxed_soln . is_feasible ())  {  // шаг 3.3 продолжить ;  // пробуем другое решение; продолжается на шаге 3 } двойной  current_objective_value  =  curr_relaxed_soln . значение ();  // v выше if  ( current_objective_value  <=  best_objective )  {  // шаг 3.4 продолжить ;  // пробуем другое решение; продолжается на шаге 3 } if  ( curr_relaxed_soln . is_integer ())  {  // шаг 3.5 best_objective  =  current_objective_value ; оптимальное_решение  =  cast_as_ILP_solution ( curr_relaxed_soln ); продолжить ;  // продолжаем с шага 3 } // текущее смягченное решение не является интегральным if  ( unting_for_cutting_planes )  {  // шаг 3.6 violated_cutting_planes  =  search_for_violated_cutting_planes ( curr_relaxed_soln ); if  ( ! violated_cutting_planes . empty ())  {  // шаг 3.6 cut_planes_found  =  истина ;  // продолжаем с шага 3.2 для  ( авто &&  cutting_plane  :  violated_cutting_planes )  { активный_лист . enqueue ( LP_relax ( curr_prob ,  Cut_plane )); } продолжить ;  // продолжаем с шага 3.2 } } // шаг 3.7: либо нарушенные режущие плоскости не найдены, либо мы их не искали авто &&  branched_problems  =  branch_partition ( curr_prob ); for  ( auto &&  branch  :  branched_problems )  { активный_лист . enqueue ( ветвь ); } продолжить ;  // продолжаем с шага 3 }  while  ( unting_for_cutting_planes  / * параметр алгоритма; см. 3.6 * / &&  cut_planes_found ); // завершаем шаг 3.2 цикл do-while }  // завершаем шаг 3, пока цикл вернуть  optim_solution ;  // шаг 4}

В приведенном выше псевдокоде, функция LP_relax, LP_solveи branch_partitionназываемая в виде подпрограмм должна быть предусмотрена как применимые к этой проблеме. Например, LP_solveможно вызвать симплексный алгоритм . Стратегии ветвления branch_partitionобсуждаются ниже.

Стратегии ветвления [ править ]

Важным шагом в алгоритме ветвления и отсечения является шаг ветвления. На этом этапе можно использовать различные эвристики ветвления. Все описанные ниже стратегии ветвления включают так называемое ветвление по переменной. ^[3] Ветвление по переменной включает выбор переменной с дробным значением в оптимальном решении текущей релаксации LP, а затем добавление ограничений и $x_{i}$ $x_{i}'$ $x_{i}\leq \left\lfloor x_{i}'\right\rfloor$ $x_{i}\geq \left\lceil x_{i}'\right\rceil$

Наиболее недопустимое ветвление: Эта стратегия ветвления выбирает переменную с дробной частью, наиболее близкой к 0,5.
Ветвление псевдозатрат: Основная идея этой стратегии состоит в том, чтобы отслеживать для каждой переменной изменение целевой функции, когда эта переменная была ранее выбрана в качестве переменной для перехода. Затем стратегия выбирает переменную, для которой прогнозируется наибольшее изменение целевой функции на основе прошлых изменений, когда она была выбрана в качестве переменной ветвления. Обратите внимание, что ветвление псевдозатрат изначально неинформативно при поиске, так как несколько переменных были разветвлены. $x_{i}$
Сильное ветвление: Сильное ветвление включает в себя проверку того, какая переменная-кандидат дает лучшее улучшение целевой функции, прежде чем фактически перейти к ним. Полное сильное ветвление проверяет все возможные переменные и может потребовать больших вычислительных ресурсов. Вычислительные затраты могут быть уменьшены за счет рассмотрения только подмножества переменных-кандидатов и не решения каждой из соответствующих релаксаций LP до завершения.

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

Ссылки [ править ]

^ Падберг, Манфред; Ринальди, Джованни (1991). "Разветвленный алгоритм решения крупномасштабных симметричных задач коммивояжера". Обзор SIAM . 33 (1): 60–100. DOI : 10.1137 / 1033004 . ISSN 0036-1445 .
^ Джон Э., Митчелл (2002). "Разветвленные алгоритмы для задач комбинаторной оптимизации" (PDF) . Справочник по прикладной оптимизации : 65–77.
^ Ахтерберг, Тобиас; Кох, Торстен; Мартин, Александр (2005). «Пересмотр правил ветвления». Письма об исследованиях операций . 33 (1): 42–54. DOI : 10.1016 / j.orl.2004.04.002 .

Внешние ссылки [ править ]

Смешанное целочисленное программирование
SCIP : фреймворк для разветвления и решателя смешанного целочисленного программирования
ABACUS - A Branch-And-CUt System - программное обеспечение с открытым исходным кодом
COIN-OR Cbc - программное обеспечение с открытым исходным кодом на GitHub

[1] Падберг, Манфред; Ринальди, Джованни (1991). "Разветвленный алгоритм решения крупномасштабных симметричных задач коммивояжера". Обзор SIAM . 33 (1): 60–100. DOI : 10.1137 / 1033004 . ISSN 0036-1445 .

[2] Джон Э., Митчелл (2002). "Разветвленные алгоритмы для задач комбинаторной оптимизации" (PDF) . Справочник по прикладной оптимизации : 65–77.

[3] Ахтерберг, Тобиас; Кох, Торстен; Мартин, Александр (2005). «Пересмотр правил ветвления». Письма об исследованиях операций . 33 (1): 42–54. DOI : 10.1016 / j.orl.2004.04.002 .

[1]