#python #gurobi
#python #gurobi
Вопрос:
Я использую Gurobi для решения проблемы. Моя цель — сравнить количество исследованных узлов в разных экземплярах. Но для этой цели точное количество исследованных узлов не важно, потому что в экземплярах разных размеров оно может быть в разных масштабах. В связи с этим я хочу найти отношение количества исследованных узлов ко всем узлам, доступным для изучения.
Я знаю, что в Gurobi я могу получить количество исследованных узлов с помощью:
model.NodeCount
Но я не знаю, как найти все доступные узлы.
Ответ №1:
Количество всех возможных узлов определить непросто. Интуитивно понятно, что это будет число всех возможных способов определения LP путем фиксации целочисленных переменных. На практике, однако, каждый решатель применяет ряд методов, чтобы никогда не требовать посещения всех этих узлов (распространение домена, обрезка, вырезка, …). Даже количество зарегистрированных открытых узлов не является хорошей или надежной мерой, поскольку оно может не отражать искомое число.
Возможно, эта статья пригодится для чтения, чтобы глубже погрузиться в тему размеров дерева с ветвями и границами:
https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7814
Комментарии:
1. На самом деле, проблема представляет собой NP-полную проблему. Моя цель состоит в том, чтобы отличать простые экземпляры от сложных на основе исследованных узлов. Я не уверен, что это правильный способ или нет, но я пробую его с помощью оптимизации в Gurobi. Позвольте мне прочитать рекомендованную вами статью.