Среда для задач целочисленного программирования
Решите небольшую задачу целочисленного линейного программирования точным методом ветвей и границ и просмотрите все узлы поиска. Лучшая точка отмечается как доказанно оптимальная, только если исследовано всё дерево.
Программа ограничена 4 000 символами и 40 строками, 8 переменными и 8 ограничениями с двумя или более переменными; лимит узлов — от 1 до 5 000, а поиск также прекращается после 3 000 000 шагов точной арифметики. Вычисления выполняются на устройстве в фоновом процессе с лимитом 15 секунд. Доступны отчёт JSON и CSV с узлами. В первой строке укажите maximize или minimize и целевую функцию. Затем записывайте по одному ограничению в каждой строке. До 4 000 символов. Проверьте настройки перед запуском.
Ваш результат
Среда для задач целочисленного программирования
- Запишите целевую функцию в первой строке, например maximize 5x + 4y.
- Записывайте каждое ограничение с новой строки, включая границы вроде x, y >= 0 и, при необходимости, строки integer x или binary z.
- Задайте лимит узлов и запустите поиск.
- Изучите статус, лучшее найденное решение, наилучшую границу и разрыв, затем скачайте отчёт JSON или CSV с узлами.
Что нужно знать
Программа ограничена 4 000 символами и 40 строками, 8 переменными и 8 ограничениями с двумя или более переменными; лимит узлов — от 1 до 5 000, а поиск также прекращается после 3 000 000 шагов точной арифметики. Вычисления выполняются на устройстве в фоновом процессе с лимитом 15 секунд. Доступны отчёт JSON и CSV с узлами.
Метод ветвей и границ
В каждом узле линейная релаксация точно решается симплекс-методом. Для целочисленной переменной с дробным значением создаются две ветви: x <= floor и x >= ceiling. Узлы отсекаются, если релаксация несовместна или не может улучшить лучшее найденное целочисленное решение. Метод: Wolsey, Integer Programming, 2-е издание, глава 7 (2020).
Что означает «доказано»
Если каждый узел решён или отсечён по точной границе, доказывается оптимальность текущего лучшего решения либо несовместность задачи. Если поиск раньше останавливается из-за лимита узлов или числа шагов, текущее решение остаётся лишь лучшей найденной точкой; в отчёте приводятся лучшая граница и разрыв между ними.
Правила ввода
По умолчанию все переменные целочисленные. Если вы объявите некоторые из них, например строкой integer x, y, целочисленными останутся только объявленные переменные, а остальные будут непрерывными. Ограничения для одной переменной становятся границами. Если релаксация не ограничена, поиск останавливается, поскольку целочисленная задача может быть неограниченной или несовместной.