Введение
Branch and cut – это метод комбинаторной оптимизации для решения задач целочисленного линейного программирования (ILP), то есть задач линейного программирования (LP), в которых некоторые или все переменные должны принимать целые значения. Метод branch and cut включает в себя выполнение алгоритма ветвей и границ и использование сечений для усиления релаксаций линейного программирования. Следует отметить, что если сечения используются только для усиления исходной релаксации LP, алгоритм называется cut and branch.
Стратегии разветвления
Важным шагом в алгоритме ветвей и границ является шаг ветвления. На этом этапе существует множество эвристик ветвления, которые могут быть использованы. Стратегии ветвления, описанные ниже, включают в себя так называемое ветвление по переменной. Ветвление по переменной включает в себя выбор переменной с дробным значением в оптимальном решении текущей LP-релаксации и затем добавление ограничений и .
Наиболее невыполнимое ветвление. Эта стратегия ветвления выбирает переменную с дробной частью, наиболее близкой к 0.5. Ветвление по псевдостоимости. Основная идея этой стратегии заключается в отслеживании для каждой переменной изменения в целевой функции, когда эта переменная была ранее выбрана в качестве переменной для ветвления. Затем стратегия выбирает переменную, которая, как прогнозируется, окажет наибольшее влияние на целевую функцию, основываясь на предыдущих изменениях, когда она была выбрана в качестве переменной для ветвления. Следует отметить, что ветвление по псевдостоимости изначально неинформативно в процессе поиска, поскольку было выполнено ветвление по небольшому числу переменных. Сильное ветвление. Сильное ветвление включает в себя проверку того, какая из переменных-кандидатов дает наилучшее улучшение целевой функции, прежде чем фактически выполнять ветвление по ней. Полное сильное ветвление проверяет все переменные-кандидаты и может быть вычислительно затратным. Вычислительные затраты можно снизить, рассматривая только подмножество переменных-кандидатов и не доводя решение каждой соответствующей LP-релаксации до конца. Существует также большое количество вариаций этих стратегий ветвления, таких как использование сильного ветвления на ранних этапах, когда ветвление по псевдостоимости относительно неинформативно, а затем переход к ветвлению по псевдостоимости позже, когда накопится достаточно истории ветвления для того, чтобы псевдостоимость стала информативной.
Most infeasible branching This branching strategy chooses the variable with the fractional part closest to 0.5. Pseudo cost branching The basic idea of this strategy is to keep track for each variable the change in the objective function when this variable was previously chosen as the variable to branch on. The strategy then chooses the variable that is predicted to have the most change on the objective function based on past changes when it was chosen as the branching variable. Note that pseudo cost branching is initially uninformative in the search since few variables have been branched on. Strong branching Strong branching involves testing which of the candidate variable gives the best improvement to the objective function before actually branching on them. Full strong branching tests all candidate variables and can be computationally expensive. The computational cost can be reduced by only considering a subset of the candidate variables and not solving each of the corresponding LP relaxations to completion. There are also a large number of variations of these branching strategies, such as using strong branching early on when pseudo cost branching is relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative.