Ветвительный механизм в B & P с использованием SCIP

Question

Я реализую алгоритм ветвления и цены в c с использованием SCIP.

Вопрос: Чтобы вызвать механизм ветвления, я использую основной механизм BRANCHEXECLP. Как SCIP знает, когда нужно разветвляться? Когда текущее релаксационное решение имеет нецелые решения, верно? Мне не нужно сообщать SCIP о вызове механизма ветвления для этого случая, правильно?

Я прошу, потому что (по большей части) мой алгоритм B & P работает хорошо. Но в какой-то момент он достигает узла, соответствующего двойному связанному решению. После решения проблемы ценообразования (и никакие столбцы не привлекательны для ввода главной проблемы) релаксационное решение на этом узле содержит нецелые решения, но механизм ветвления не вызывается. Запуск просто завершается. Любая идея о том, что здесь происходит?

Спасибо, Роб Карри

Answer 1

Я думаю, вы проверили при ценообразовании, что существуют дробные переменные в текущем решении LP?

И двойная привязка в этом узле равна глобальной двойной границе? Вы отметили свою цель, чтобы иметь только интегральные значения? В этом случае, если двойная привязка достаточно близка к первичной границе, которая округляет ее, дает такое же число, SCIP просто отрежет узел. Возможно, SCIP нашел новое решение после вашей цены, которое сразу же оказалось оптимальным благодаря текущей глобальной двойной привязке? SCIP автоматически запускает некоторые простые эвристики округления после каждого решенного LP в цикле ценообразования.