Как получить глобальную нижнюю границу в рамках COIN BCP
В настоящее время я работаю над алгоритмом ветвления и цены (BAP), используя платформу COIN OR BCP. Это хороший фреймворк, но немного устаревший и документация не очень хорошая. Я надеюсь, что кто-то здесь сможет ответить на мой вопрос.
Мой алгоритм BAP работает нормально, но я заметил, что то, что я считал глобальной нижней границей, на самом деле было только нижней границей для конкретного узла в ветви и в дереве цен. Иногда я получаю слегка отрицательные пробелы 🙂
Таким образом, я копался во внутренних частях фреймворка в поисках того, как получить глобально допустимую нижнюю границу. Как ни странно, похоже, что это не особенность фреймворка!
Мне нужно получить нижнюю границу в своем древовидном классе (полученную из BCP_tm_user), чтобы сообщить о пробелах в решении.
Решение
Я не смог получить глобальные границы, используя хороший и чистый подход. Однако я смог получить эти значения, используя косвенный подход. Я поделюсь некоторыми соображениями ниже.
Нижняя граница
Кажется, что менеджер дерева BCP следит за нижними границами в узлах дерева в многоуровневой структуре данных std. Меня озадачивает, почему они отслеживают больше, чем самые низкие, потому что в любое время им нужна только лучшая нижняя граница. Доступ к мультиструктурной структуре данных возможен в * BCP_tm_user *, однако эти значения не являются глобальными нижними границами. Поэтому я попытался получить корневой LP, связанный с переопределением каждой возможной виртуальной функции (особенно * display_node_information *) в * BCP_tm_user *. Идея заключалась в том, чтобы прочитать лучшую нижнюю границу сразу после того, как корневой узел был решен. К сожалению, это был неудачный подход, лучшее значение в мультимножестве — не привязка к корню LP.
Верхняя граница
Точно так же я не смог получить хороший метод для извлечения наилучшей верхней границы (т.е. возможного решения) в * BCP_tm_user *. Очевидный метод и простой метод получения верхней границы — переопределить * display_feasible_solution * и извлечь значение здесь. Однако есть предостережение для этой аппроксимации: если вы решили удалить все (или большинство) выходных данных BCP, то * display_feasible_solution * больше не вызывается!
Мое решение
Обе границы доступны в классе * BCP_lp_user *, если вы переопределите * select_branching_candidates *. Вызов * upper_bound () * здесь даст вам наилучшую доступную верхнюю границу! И сгенерированное значение решения для релаксации LP (если столбцов с отрицательной сниженной стоимостью не существует) является глобальной нижней границей в корневом узле. Вы знаете, что это корневой узел, если выполняется * this-> current_level () == 0 *. Если вам нужны границы в менеджере дерева, я предлагаю вам передать (упаковать / распаковать) их вместе с решениями, которые вы отправляете.
Другие решения
Вы можете перебрать дерево и найти нижнюю нижнюю границу среди живых узлов:
BCP_tree &search_tree = getTmProblemPointer().search_tree;
double global_lower_bound = BCP_DBL_MAX;
for (auto itt = search_tree.begin(); itt != search_tree.end(); itt++) {
BCP_tm_node *tm_node = *itt;
if (tm_node == NULL || tm_node->status == BCP_ProcessedNode) continue;
double trueLB = tm_node->getTrueLB();
global_lower_bound = min(global_lower_bound, trueLB);
}