Среда за целочислено програмиране
Решете малка целочислена линейна програма с точно branch-and-bound и прегледайте всеки възел на търсенето. Най-добрата точка се обявява за доказано оптимална само когато е обходено цялото дърво.
Програмите са ограничени до 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.
- Задайте лимита на възлите и стартирайте търсенето.
- Прегледайте състоянието, incumbent, най-добрата граница и разликата, след което изтеглете JSON отчета или CSV файла с възлите.
Какво да очаквате
Програмите са ограничени до 4 000 знака и 40 реда, 8 променливи и 8 ограничения с две или повече променливи; лимитът на възлите е от 1 до 5 000, а търсенето спира и след 3 000 000 стъпки точна аритметика. Всичко се изчислява на устройството във фонов режим с лимит 15 секунди. Изтегляния: JSON отчет и CSV с възлите.
Branch and bound
Всеки възел решава точно линейната релаксация чрез симплексния метод. Дробна целочислена променлива се разделя на два клона: x <= floor и x >= ceiling. Възли се премахват, когато релаксацията е неизпълнима или не може да подобри най-доброто намерено цяло решение. Метод: Wolsey, Integer Programming, 2-ро издание, глава 7 (2020).
Какво означава „доказано“
Когато всеки възел е решен или премахнат с точна граница, incumbent е доказано оптимален или задачата е доказано неизпълнима. Ако лимитът на възлите или стъпките спре търсенето по-рано, incumbent е само най-добрата намерена до момента точка, а отчетът показва най-добрата граница и разликата между тях.
Правила за въвеждане
Променливите са цели, освен ако не посочите някои с integer x, y; тогава останалите са непрекъснати. Ограниченията с една променлива стават граници. Неограничена релаксация спира търсенето, защото целочислената програма може да е неограничена или неизпълнима.