Середовище цілочислового програмування
Розв'яжіть невелику цілочислову лінійну програму точним методом гілок і меж та перегляньте кожен вузол пошуку. Найкращу точку оголошено оптимальною лише після обходу всього дерева.
Програми обмежено 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 <= округлення вниз і x >= округлення вгору. Вузли відсікають, якщо їхня релаксація несумісна або не може поліпшити найкращу знайдену цілочислову точку. Метод: Wolsey, Integer Programming, 2-ге видання, розділ 7 (2020).
Що означає «доведено»
Якщо кожен вузол розв'язано або відсічено за точною межею, доведено оптимальність поточного найкращого розв'язку або несумісність задачі. Якщо пошук раніше зупиняється через ліміт вузлів або кроків, поточна точка лише найкраща з досі знайдених, а у звіті наведено найкращу межу та розрив між ними.
Правила введення
За замовчуванням змінні цілочислові. Якщо деякі змінні оголосити командою integer x, y, вони будуть цілочисловими, а решта — неперервними. Обмеження з однією змінною стають межами. Якщо релаксація необмежена, пошук зупиняється, оскільки цілочислова програма може бути необмеженою або несумісною.