Как docplex находит лучший предел?

Question

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

Answer 1

Наилучшая оценка исходит от решения LP.Это решение, которое было бы возможным, если бы переменным не требовалось иметь целочисленные значения.Ни одно целочисленное решение не может иметь лучшего объективного значения, чем это «расслабленное» решение, поэтому оно обеспечивает действительную оценку цели.Поскольку CPLEX исследует и удаляет части дерева B & B, он может обновлять границу, используя последовательно лучшие значения.