Количество уровней в ветке и связанном дереве

Question

Количество уровней в ветке и связанном дереве

Учитывая оптимизацию ILP (целочисленное линейное программирование) с n целочисленными переменными и m ограничениями и реализацию ветви и связанного дерева для решения канонической задачи,

Сколько уровней (высота дерева) требуется дереву, чтобы достичь полностью целочисленного оптимального решения?
Сколько ветвей требуется алгоритму, чтобы достичь оптимального решения с целыми числами?

0

ip integer-programming branch-and-bound

Источник

user2594157 24 фев '14 в 16:29

1 ответ

Другие вопросы по тегам ip integer-programming branch-and-bound

user2108433 25 фев '14 в 08:20 2014-02-25 08:20 · Answer 1 · 2014-02-25 08:20

На этот вопрос сложно ответить - оба могут быть равны нулю, если вам действительно повезет, или в худшем случае "высота" (или глубина) может быть равна числу целочисленных переменных n. Количество веток может быть намного больше... все зависит от проблемы и решателя.