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

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

Содержание

• 1 Алгоритм
  • 1.1 Псевдокод
• 2 Стратегии ветвления
• 3 Ссылки
• 4 Внешние ссылки

Алгоритм

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

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

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

Алгоритм кратко описан ниже.

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

Псевдокод

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

1 // Псевдокод решения ветвления и отсечения ILP, предполагая, что цель - максимизировать 2 ILP_solution branch_and_cut_ILP (IntegerLinearProgram initial_problem) {3 очередь active_list; // L, выше 4 active_list.enqueue (initial_problem); // шаг 1 5 // шаг 2 6 ILP_solution optim_solution; // это будет содержать x * больше 7 double best_objective = -std :: numeric_limits :: infinity; // сохранит v * выше 8 while (! active_list.empty ()) {// шаг 3 выше 9 LinearProgram curr_prob = active_list.dequeue (); // шаг 3.1 10 do {// шаги 3.2–3.7 11 RelaxedLinearProgram relaxed_prob = LP_relax (curr_prob); // шаг 3.2 12 LP_solution curr_relaxed_soln = LP_solve (relaxed_prob); // это x больше 13 bool cut_planes_found = false; 14 if (! Curr_relaxed_soln.is_feasible ()) {// шаг 3.3 15 continue; // пробуем другое решение; продолжается на шаге 3 16} 17 double current_objective_value = curr_relaxed_soln.value (); // v выше 18 if (current_objective_value <= best_objective) { // step 3.4 19 continue; // try another solution; continues at step 3 20 } 21 if (curr_relaxed_soln.is_integer()) { // step 3.5 22 best_objective = current_objective_value; 23 optimal_solution = cast_as_ILP_solution(curr_relaxed_soln); 24 continue; // continues at step 3 25 } 26 // current relaxed solution isn't integral 27 if (hunting_for_cutting_planes) { // step 3.6 28 violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln); 29 if (!violated_cutting_planes.empty()) { // step 3.6 30 cutting_planes_found = true; // will continue at step 3.2 31 for (autocutting_plane : violated_cutting_planes) { 32 active_list.enqueue(LP_relax(curr_prob, cutting_plane)); 33 } 34 continue; // continues at step 3.2 35 } 36 } 37 // step 3.7: either violated cutting planes not found, or we weren't looking for them 38 autobranched_problems = branch_partition(curr_prob); 39 for (autobranch : branched_problems) { 40 active_list.enqueue(branch); 41 } 42 continue; // continues at step 3 43 } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */ 44 cutting_planes_found); 45 // end step 3.2 do-while loop 46 } // end step 3 while loop 47 return optimal_solution; // step 4 48 }

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

Стратегии ветвления

Важным шагом в алгоритме ветвления и отсечения является шаг ветвления. На этом шаге можно использовать множество эвристик ветвления. Все описанные ниже стратегии ветвления включают так называемое ветвление по переменной. Ветвление по переменной включает выбор переменной $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$с дробным значением, $xi\; \prime \; \{\backslash \; displaystyle\; x\_\; \{i\}\; \text{'}\; \}$, в оптимальном решении текущей релаксации LP с последующим добавлением ограничений $xi\; \le \; \lfloor \; xi\; \prime \; \rfloor \; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; leq\; \backslash \; left\; \backslash \; lfloor\; x\_\; \{i\}\; \text{'}\backslash \; right\; \backslash \; rfloor\}$и $xi\; \ge \; \lceil \; xi\; \prime \; \rceil \; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; geq\; \backslash \; left\; \backslash \; lceil\; x\_\; \{i\}\; \text{'}\backslash \; right\; \backslash \; rceil\}$

Наиболее недопустимое ветвление

Эта стратегия ветвления выбирает переменную с дробной частью, ближайшей к 0,5.

Ветвление псевдозатрат

Основная идея этой стратегии - отслеживать для каждой переменной $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$изменение целевая функция, когда эта переменная была ранее выбрана в качестве переменной для перехода. Затем стратегия выбирает переменную, для которой прогнозируется наибольшее изменение целевой функции на основе прошлых изменений, когда она была выбрана в качестве переменной ветвления. Обратите внимание, что ветвление по псевдо-стоимости изначально неинформативно при поиске, поскольку несколько переменных были разветвлены.

Сильное ветвление

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

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

Литература

Внешние ссылки

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