Лекція 09. Цілочисельна та бінарна оптимізація: MILP і CP-SAT

Коротко про лекцію

Ви побачите, коли дробовий розв’язок втрачає предметний зміст і потрібні цілочисельні або бінарні змінні. Лекція пояснює MILP, LP-релаксацію, обмеження вибору та причини, через які просте округлення може зламати план.

Практичний сенс. Дискретні рішення описують вибір проєктів, кількість машин, призначення працівників і розклади. Цілочисельні та бінарні змінні роблять математичну модель узгодженою з такими рішеннями.

Постановка та базові поняття

1. Чому неперервного LP інколи недостатньо

У неперервному LP змінна може мати дробове значення. Для літрів або тонн це природно. Для кількості автомобілів, працівників або вибору проєкту дробове значення не має предметного змісту.

Наприклад, значення \(x=3.7\) може описувати 3.7 тонни матеріалу. Воно не може означати 3.7 автомобіля в звичайному плані закупівлі.

Тому математична модель повинна явно фіксувати дискретність.

1.1. Розшифрування назв MILP, лінійна релаксація та CP-SAT

MILP — усталене міжнародне скорочення для змішаного цілочисельного лінійного програмування. У такій моделі частина змінних може бути неперервною, а частина повинна бути цілою або бінарною. Скорочення залишаємо, бо саме так цей клас позначають у документації розв’язувачів.

Щоб оцінити складну цілочисельну задачу, тимчасово прибирають вимогу цілочисельності. Отриману простішу задачу називають лінійною релаксацією. Вона дає межу для цільової функції та допомагає відкидати безперспективні гілки.

Метод гілок і меж систематично розділяє простір рішень на підзадачі та використовує такі межі. CP-SAT — назва розв’язувача OR-Tools для задач із цілими змінними та логічними обмеженнями. Назву API зберігаємо, а математичний зміст пояснюємо українською.

2. Цілочисельна змінна

Цілочисельна змінна належить множині цілих чисел:

\[ x_i\in\mathbb{Z} \]

Для невід’ємної кількості використовують:

\[ x_i\in\mathbb{Z}_{\ge0} \]

Такі змінні описують кількість машин, коробок, змін, працівників або одиниць обладнання.

3. Бінарна змінна

Бінарна змінна має тільки два значення:

\[ x_i\in\{0,1\} \]

Зміст часто читається так:

\[ x_i=1 \]

означає «варіант обрано», а:

\[ x_i=0 \]

означає «варіант не обрано».

Бінарні змінні зручні для логічних рішень, призначень і відкриття об’єктів.

4. Наскрізна задача вибору проєктів

Компанія розглядає три проєкти.

Проєкт	Витрати	Користь
1	5	8
2	4	6
3	3	5

Доступний бюджет:

\[ B=7 \]

Потрібно вибрати набір проєктів із максимальною сумарною користю.

5. Вводимо бінарні змінні

\[ x_1= \begin{cases} 1, & \text{проєкт 1 обрано},\\ 0, & \text{проєкт 1 не обрано} \end{cases} \]

Аналогічно вводимо \(x_2\) та \(x_3\).

Усі змінні мають домен:

\[ x_i\in\{0,1\} \]

6. Цільова функція

Сумарна користь:

\[ Z=8x_1+6x_2+5x_3 \]

Потрібно максимізувати:

\[ Z\rightarrow\max \]

7. Бюджетне обмеження

Сумарні витрати:

\[ 5x_1+4x_2+3x_3 \]

Вони не повинні перевищувати бюджет:

\[ 5x_1+4x_2+3x_3\le7 \]

Повна модель:

\[ \max 8x_1+6x_2+5x_3 \]

за умов:

\[ 5x_1+4x_2+3x_3\le7 \]

\[ x_1,x_2,x_3\in\{0,1\} \]

Математична логіка

8. Повний перебір маленького прикладу

Три бінарні змінні дають:

\[ 2^3=8 \]

можливих комбінацій.

\(x_1\)	\(x_2\)	\(x_3\)	Витрати	Користь	Допустимість
0	0	0	0	0	так
1	0	0	5	8	так
0	1	0	4	6	так
0	0	1	3	5	так
1	1	0	9	14	ні
1	0	1	8	13	ні
0	1	1	7	11	так
1	1	1	12	19	ні

Найкращий допустимий варіант:

\[ x^*= \begin{pmatrix} 0\\ 1\\ 1 \end{pmatrix} \]

Його користь:

\[ Z^*=11 \]

9. LP-релаксація

Якщо прибрати цілочисельність і дозволити:

\[ 0\le x_i\le1 \]

отримаємо LP-релаксацію.

Для нашої задачі один оптимум релаксації:

\[ x^{LP}= \begin{pmatrix} 0.8\\ 0\\ 1 \end{pmatrix} \]

Перевірка бюджету:

\[ 5\cdot0.8+3\cdot1=7 \]

Користь:

\[ 8\cdot0.8+5=11.4 \]

Це значення вище за 11, бо релаксація має ширшу допустиму множину.

10. Чому округлення релаксації не є методом

Округлимо \(0.8\) до 1:

\[ (1,0,1) \]

Витрати:

\[ 5+3=8 \]

Але бюджет дорівнює 7:

\[ 8>7 \]

Отже, округлення створило недопустимий план.

Округлення вниз дає \((0,0,1)\) з користю 5, хоча допустимий план \((0,1,1)\) має користь 11.

Тому інтегральність повинна бути частиною алгоритму пошуку.

11. Загальна MILP-модель

Змішане цілочисельне лінійне програмування (MILP, змішане цілочисельне лінійне програмування) має лінійну ціль і лінійні обмеження, але частина змінних повинна бути цілою.

Загальна форма:

\[ \min c^Tx \]

за умов:

\[ b_l\le Ax\le b_u \]

\[ l\le x\le u \]

Для частини індексів:

\[ x_i\in\mathbb{Z} \]

12. Ідея метод гілок і меж

Метод гілок і меж використовує LP-релаксацію як джерело межі.

Якщо релаксація вже дає цілі значення, поточний вузол може завершитися оптимальним цілочисельним кандидатом.

Якщо змінна дробова, наприклад:

\[ x_1=0.8 \]

простір розділяють на гілки. Для бінарної змінної це природно:

\[ x_1=0 \]

і:

\[ x_1=1 \]

Кожна гілка породжує нову підзадачу.

13. Для чого потрібна межа

LP-релаксація задачі максимізації дає верхню межу для цілочисельної цілі.

У нашому прикладі:

\[ Z_{LP}=11.4 \]

Будь-який бінарний план має:

\[ Z_{IP}\le11.4 \]

Знайдений допустимий бінарний план з \(Z=11\) дає нижню межу.

Коли межі збігаються достатньо близько, чисельний розв’язувач може довести оптимальність.

14. Що таке MIP розрив

MIP розрив вимірює відстань між найкращим відомим допустимим цілочисельним рішенням і глобальною межею.

Конкретна формула може залежати від чисельного розв’язувача, тому в навчальному аудиті важливо читати документацію інструмента.

Малий розрив означає, що знайдений план близький до доведеної межі. Нульовий розрив разом із відповідним статусом означає доведену оптимальність.

15. Логічні зв’язки через бінарні змінні

Бінарна змінна може активувати інше рішення.

Наприклад, якщо проєкт 3 дозволено тільки разом із проєктом 2:

\[ x_3\le x_2 \]

Якщо \(x_3=1\), нерівність змушує \(x_2=1\).

Якщо можна вибрати не більше одного з двох проєктів:

\[ x_1+x_2\le1 \]

Такі конструкції перетворюють словесну логіку на лінійні обмеження.

16. Задача призначення

Бінарна змінна \(x_{ij}\) може означати призначення працівника \(i\) на завдання \(j\).

Для кожного працівника:

\[ \sum_j x_{ij}=1 \]

Для кожного завдання:

\[ \sum_i x_{ij}=1 \]

Ціль може мінімізувати сумарний час або вартість.

Це одна з найпоширеніших структур дискретної оптимізації.

Алгоритм і покроковий розбір

17. Робочий маршрут дискретної моделі

Для прикладної задачі дійте так:

1. визначте, які рішення справді дискретні;
2. оберіть домен кожної змінної;
3. запишіть лінійну ціль;
4. формалізуйте ресурсні й логічні обмеження;
5. перевірте маленький ручний приклад;
6. розв’яжіть модель чисельним розв’язувачем;
7. перевірте цілочисельність та всі обмеження;
8. інтерпретуйте статус і розрив.

18. Візуальне порівняння релаксації та бінарного рішення

Релаксація має вище значення 11.4, але використовує дробову частину першого проєкту.

Бінарний оптимум вибирає проєкти 2 і 3 та точно використовує бюджет 7.

Програмна реалізація та перевірка

19. MILP через SciPy

SciPy milp мінімізує передану ціль. Тому для максимізації користі використовуємо від’ємні коефіцієнти.

# Імпортуємо NumPy, SciPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np
from scipy.optimize import Bounds
from scipy.optimize import LinearConstraint
from scipy.optimize import milp


# Задаємо коефіцієнти цільової функції в тому самому порядку, що й компоненти вектора змінних.
benefit = np.array([
    8.0,
    6.0,
    5.0,
])

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
cost = np.array([
    5.0,
    4.0,
    3.0,
])

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
budget = 7.0

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
constraints = LinearConstraint(
    cost,
    -np.inf,
    budget,
)

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
bounds = Bounds(
    lb=np.zeros(3),
    ub=np.ones(3),
)

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
integrality = np.ones(3)

# Запускаємо MILP-розв’язувач і явно передаємо ціль, цілочисельність, межі та лінійні обмеження.
result = milp(
    c=-benefit,
    integrality=integrality,
    bounds=bounds,
    constraints=constraints,
)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not result.success:
    raise RuntimeError(result.message)

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
selection = np.rint(result.x).astype(int)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Вибір:", selection)
print("Користь:", benefit @ selection)
print("Витрати:", cost @ selection)

Очікувано:

Вибір: [0 1 1]
Користь: 11.0
Витрати: 7.0

integrality=1 означає, що відповідна змінна повинна бути цілою.

20. CP-SAT через OR-Tools

CP-SAT особливо зручний для бінарної логіки, призначень і розкладів.

# Імпортуємо OR-Tools для обчислень, розв’язання моделі та її перевірки.
from ortools.sat.python import cp_model


# Створюємо CP-SAT модель, до якої далі додамо бінарні змінні, обмеження та ціль.
model = cp_model.CpModel()

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
project_1 = model.new_bool_var("project_1")
project_2 = model.new_bool_var("project_2")
project_3 = model.new_bool_var("project_3")

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
model.add(
    5 * project_1
    + 4 * project_2
    + 3 * project_3
    <= 7
)

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
model.maximize(
    8 * project_1
    + 6 * project_2
    + 5 * project_3
)

# Запускаємо CP-SAT розв’язувач і далі перевіряємо його статус перед читанням змінних.
solver = cp_model.CpSolver()
status = solver.solve(model)

# Перевіряємо умову алгоритму перед вибором наступної гілки обчислень.
if status not in (
    cp_model.OPTIMAL,
    cp_model.FEASIBLE,
):
    raise RuntimeError("Розв'язок не знайдено")

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
selection = [
    solver.value(project_1),
    solver.value(project_2),
    solver.value(project_3),
]

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Вибір:", selection)
print("Status:", solver.status_name(status))

CP-SAT працює з цілими коефіцієнтами та цілими змінними. Для поточної задачі всі дані вже цілі.

21. Незалежна перевірка результату

Для \(x=(0,1,1)^T\):

\[ 5\cdot0+4\cdot1+3\cdot1=7\le7 \]

Цілочисельність:

\[ x_i\in\{0,1\} \]

Ціль:

\[ 8\cdot0+6\cdot1+5\cdot1=11 \]

Ручний перебір восьми варіантів підтверджує глобальну оптимальність маленького прикладу.

Інтерпретація, межі та підсумок

22. Коли обирати MILP

MILP природний для моделей з лінійною ціллю, лінійними ресурсними обмеженнями та інтегральністю.

Приклади: вибір інвестицій, виробничі партії, відкриття об’єктів, логістичні рішення.

23. Коли доречний CP-SAT

CP-SAT особливо сильний, коли модель містить багато дискретної логіки, умов, призначень і часових обмежень.

Він працює над цілими числами. Дробові коефіцієнти потрібно масштабувати до цілих значень з контрольованою точністю.

24. Статус має точний зміст

Для CP-SAT статус OPTIMAL означає доведений оптимум.

FEASIBLE означає, що допустиме рішення знайдене, але оптимальність ще не доведена.

INFEASIBLE означає доведену відсутність допустимого рішення.

UNKNOWN потребує окремого аналізу причин завершення, наприклад часового ліміту.

25. Типова помилка

Типова помилка. Дробовий LP-розв’язок округляють до найближчих цілих значень. Після округлення план може стати недопустимим або втратити значну частину цілі.

25.1. Чому дискретна допустима множина має іншу геометрію

У неперервному LP допустима множина містить усі точки всередині многокутника або багатовимірного многогранника.

Після введення цілочисельність частина цих точок зникає. Для бінарних змінних залишаються тільки вершини гіперкуба з координатами 0 або 1.

У задачі трьох проєктів неперервна релаксація дозволяє точку:

\[ (0.8,0,1) \]

Бінарна модель її відкидає. Тому оптимум дискретної задачі може лежати далеко від оптимуму релаксації.

Це геометричне пояснення показує, чому звичайний розв’язувач лінійного програмування і наступне округлення не є еквівалентом MILP.

25.2. Розрив цілочисельності

Різниця між найкращим значенням LP-релаксації та найкращим цілочисельним значенням називається розрив цілочисельності у широкому навчальному сенсі.

Для нашої максимізації:

\[ Z_{LP}=11.4 \]

\[ Z_{IP}=11 \]

Абсолютна різниця:

\[ 11.4-11=0.4 \]

Релаксація дає верхню межу, але ця межа не обов’язково досяжна дискретним планом.

Чим сильніша математична формуляція, тим кориснішою може бути релаксаційна межа для метод гілок і меж.

25.3. Метод гілок і меж на нашому прикладі

Розглянемо дробову змінну \(x_1=0.8\) у LP-релаксації. Розгалуження для бінарної змінної створює два випадки.

Перша гілка:

\[ x_1=0 \]

Тоді залишаються проєкти 2 і 3. Обидва разом коштують:

\[ 4+3=7 \]

і дають користь:

\[ 6+5=11 \]

Отже, гілка дає допустимий цілочисельний план із ціллю 11.

Друга гілка:

\[ x_1=1 \]

Після вибору першого проєкту залишається бюджет:

\[ 7-5=2 \]

Проєкти 2 і 3 коштують 4 та 3, тому жоден з них уже не поміщається. Найкращий план гілки має користь 8.

Порівняння гілок одразу доводить, що \((0,1,1)\) є кращим.

На великих задачах чисельний розв’язувач виконує таку логіку автоматично, використовуючи додаткові межі, відсікання і евристики.

25.4. Найкращий знайдений цілочисельний розв’язок і межа

Під час метод гілок і меж чисельний розв’язувач зберігає найкраще знайдене допустиме дискретне рішення. Його часто називають найкращий знайдений цілочисельний розв’язок.

Для задачі максимізації найкращий знайдений цілочисельний розв’язок дає нижню межу на оптимальне значення.

LP-релаксації відкритих вузлів дають верхні межі. Якщо верхня межа певної гілки вже не краща за найкращий знайдений цілочисельний розв’язок, цю гілку можна відкинути.

Таке відсікання зменшує кількість комбінацій, які потрібно досліджувати явно.

25.5. Логічне правило «якщо, то»

Бінарні змінні дозволяють формалізувати залежності.

Правило «якщо проєкт 3 обрано, то проєкт 2 теж обрано» записується:

\[ x_3\le x_2 \]

Перевіримо всі два можливі значення \(x_3\).

Якщо \(x_3=0\), нерівність не змушує \(x_2\) до конкретного значення.

Якщо \(x_3=1\), маємо:

\[ 1\le x_2 \]

а бінарний домен залишає тільки \(x_2=1\).

Ця коротка нерівність точно кодує словесну залежність.

25.6. Правило взаємного виключення

Якщо проєкти 1 і 2 конфліктують, можна записати:

\[ x_1+x_2\le1 \]

Допустимими залишаються комбінації \((0,0)\), \((1,0)\) та \((0,1)\).

Комбінація \((1,1)\) порушує нерівність.

Для вибору рівно одного варіанта використовують:

\[ x_1+x_2=1 \]

Така різниця між «не більше одного» та «рівно один» має прямий предметний зміст.

25.7. Умова активації через велику константу

Іноді бінарна змінна керує неперервною величиною.

Нехай \(q\) — обсяг виробництва, а \(y\) показує, чи відкрито виробничу лінію.

Зв’язок:

\[ 0\le q\le My \]

Якщо \(y=0\), отримуємо \(q=0\).

Якщо \(y=1\), обсяг може змінюватися до \(M\).

Константа \(M\) повинна мати реалістичну верхню межу. Надмірно велике \(M\) погіршує чисельні межі та може ускладнювати розв’язування.

25.8. Чому CP-SAT любить цілі числа

CP-SAT будує обмеження оптимізація модель над цілими змінними. Бінарна змінна є окремим зручним випадком цілочисельної змінної.

Якщо вихідний коефіцієнт дорівнює 2.5, його потрібно масштабувати. Наприклад, множення на 10 дає 25.

Таке масштабування повинно бути однаковим для всіх пов’язаних членів обмеження.

Після масштабування потрібно перевірити, що математичний зміст не змінився через грубе округлення.

25.9. MILP і CP-SAT: одна задача, різний акцент

MILP природно працює з лінійними цілями та обмеженнями. Частина змінних може бути неперервною, а частина — цілою.

CP-SAT працює з цілими змінними та добре виражає логіку, призначення, інтервали й складні комбінаторний обмеження.

Для простого вибору трьох проєктів обидва інструменти розв’язують задачу без труднощів.

У складному розкладі з часовими інтервалами CP-SAT може мати природніший модельний API. У моделі з неперервними потоками та кількома цілочисельними перемикачами MILP часто є прямішим вибором.

25.10. Перевірка бінарності через нев’язка

Після чисельного розв’язувача можна обчислити:

\[ r_i^{bin}=\min(|x_i|,|x_i-1|) \]

Для правильного бінарного значення нев’язка дорівнює нулю.

У загальній цілочисельній моделі зручніше:

\[ r_i^{int}=|x_i-\operatorname{round}(x_i)| \]

Максимальна похибка:

\[ r_{int}=\max_i r_i^{int} \]

Чисельно приймаємо цілочисельність, якщо:

\[ r_{int}\le\varepsilon \]

25.11. Верифікація проєктного рішення

Для вектора:

\[ x=(0,1,1)^T \]

перевіряємо межі змінних:

\[ 0\le x_i\le1 \]

цілочисельність:

\[ x_i\in\mathbb{Z} \]

бюджет:

\[ 5x_1+4x_2+3x_3=7\le7 \]

і ціль:

\[ 8x_1+6x_2+5x_3=11 \]

Для маленької задачі повний перебір восьми комбінацій є незалежним сертифікатом оптимальності.

25.12. Чому «допустимий» та «оптимальний» статус потрібно розрізняти

Дискретний чисельний розв’язувач може зупинитися через часовий ліміт до завершення доказу оптимальності.

У такій ситуації він може мати хороший допустимий план і невідому кращу альтернативу.

Тому поле статус є частиною змісту результату.

Для CP-SAT FEASIBLE означає знайдене допустиме рішення. OPTIMAL означає, що чисельний розв’язувач також довів відсутність кращого рішення.

У звіті ці два статуси не можна зводити до одного слова «успіх».

25.13. Практичний контракт дискретного результату

Для MILP або CP-SAT корисно зберігати:

STATUS
X
OBJECTIVE
MAX_CONSTRAINT_VIOLATION
INTEGRALITY_RESIDUAL
BEST_BOUND
GAP

Конкретні поля BEST_BOUND і GAP залежать від API чисельного розв’язувача.

Математична частина перевірки залишається стабільною: домен змінних, усі обмеження та повторне обчислення цілі.

25.14. Межі маленького повного перебору

Повний перебір зручний для трьох бінарних змінних, бо маємо тільки 8 комбінацій.

Для 30 бінарних змінних кількість варіантів дорівнює:

\[ 2^{30}=1\,073\,741\,824 \]

Це вже понад мільярд комбінацій.

Тому навчальний перебір пояснює математичний зміст, а практичний чисельний розв’язувач використовує розумні межі, розгалуження й відсікання.

25.15. Перевірка всіх восьми комбінацій як навчальний еталон

Для трьох бінарних змінних повний перебір залишається корисним навчальним інструментом. Він дає точний еталон для чисельного розв’язувача.

Можна записати множину:

\[ \mathcal{X}=\{0,1\}^3 \]

Для кожного \(x\in\mathcal{X}\) обчислюємо бюджетну ліву частину:

\[ B(x)=5x_1+4x_2+3x_3 \]

і користь:

\[ Z(x)=8x_1+6x_2+5x_3 \]

До порівняння цілі допускаються тільки варіанти з:

\[ B(x)\le7 \]

Цей порядок принциповий. Спочатку допустимість, потім цільова функція.

У великих задачах повний перебір стає неможливим, але логіка перевірки залишається тією самою.

25.16. Чому бінарна змінна є математично сильнішою за текстову позначку

У звичайній таблиці можна написати «так/ні». Чисельний розв’язувач не розуміє цей текст як обмеження.

Бінарна змінна переводить рішення в арифметику. Тоді користь обраного проєкту автоматично дорівнює \(p_ix_i\), а витрата бюджету — \(c_ix_i\).

Якщо \(x_i=0\), обидва внески зникають. Якщо \(x_i=1\), вони включаються повністю.

Така модель зменшує кількість окремих умов у коді й робить логіку перевірюваною формулами.

25.17. Приклад вимоги «обрати щонайменше один»

Нехай потрібно реалізувати хоча б один із трьох проєктів.

Тоді додаємо:

\[ x_1+x_2+x_3\ge1 \]

Якщо дозволено рівно два:

\[ x_1+x_2+x_3=2 \]

Якщо дозволено не більше двох:

\[ x_1+x_2+x_3\le2 \]

Три словесні формулювання дуже схожі, але задають різні допустимі множини. Тому знак нерівності потрібно виводити з предметного правила.

25.18. Приклад альтернативи «або один, або інший»

Для взаємовиключних проєктів 1 і 2 можна вимагати рівно один вибір:

\[ x_1+x_2=1 \]

Якщо обидва можна пропустити, але разом їх брати заборонено:

\[ x_1+x_2\le1 \]

Ця різниця часто виникає у призначеннях, виборі технології або резервному плануванні.

25.19. Перевірка логічних обмеження після чисельного розв’язувача

Логічні обмеження потрібно перевіряти так само, як ресурсні.

Для правила:

\[ x_3\le x_2 \]

знаковий нев’язка можна визначити:

\[ r=x_3-x_2 \]

Порушення:

\[ v=\max(r,0) \]

Для взаємного виключення:

\[ x_1+x_2\le1 \]

перевіряємо:

\[ v=\max(x_1+x_2-1,0) \]

Тому навіть словесна бізнес-логіка завершується числовим нев’язка.

25.20. Що означає релаксація межа у максимізації

LP-релаксація має ширшу допустиму множину. Вона містить усі бінарні плани та додаткові дробові точки.

Тому максимум релаксації не може бути меншим за максимум бінарної задачі:

\[ Z_{LP}\ge Z_{IP} \]

У нашому прикладі:

\[ 11.4\ge11 \]

Ця нерівність пояснює роль LP-релаксація як верхньої межі в метод гілок і меж для максимізації.

Для мінімізації напрям змінюється: релаксація дає нижню межу.

25.21. Чому чисельний розв’язувач може працювати довше на дискретній задачі

Неперервна LP має опуклу геометрію, і сучасні алгоритми ефективно використовують цю структуру.

Цілочисельність розриває допустиму область на дискретний набір точок. Чисельний розв’язувач повинен одночасно знаходити хороші допустимі плани та доводити, що кращих немає.

Тому час розв’язання сильно залежить від кількості змінних, структури обмеження і якості релаксаційних меж.

Дві моделі з однаковою кількістю змінних можуть мати дуже різну складність.

25.22. Практичне рішення при часовому ліміті

У реальній задачі чисельний розв’язувач інколи зупиняють за часовим лімітом.

Якщо вже знайдений допустимий план, він може бути корисним для прийняття рішення. Проте його потрібно чесно позначити як допустимий, якщо оптимальність ще не доведена.

У звіті варто зберегти найкраще значення, межа і розрив. Це показує, наскільки сильним є поточний результат.

Для навчальної маленької задачі ми очікуємо статус оптимальності, бо простір пошуку дуже малий.

25.23. Модельна дисципліна перед CP-SAT

Перед створенням CpModel корисно виписати математичні домени й обмеження на папері.

Наприклад:

\[ x_i\in\{0,1\} \]

\[ 5x_1+4x_2+3x_3\le7 \]

\[ \max 8x_1+6x_2+5x_3 \]

Після цього кожний рядок коду має пряму математичну відповідність.

Такий підхід полегшує аудит. Якщо чисельний розв’язувач повертає несподіваний план, можна порівняти модельний код із трьома формулами, а не шукати помилку в довгому процедурному коді.

25.24. Перевірка домену до чисельного розв’язувача

Домен змінної варто записати до побудови коду. Для бінарного рішення це \(\{0,1\}\). Для кількості машин це можуть бути цілі значення від 0 до 20.

Такий запис одразу показує, чи підходить неперервний LP. Якщо предметний домен дискретний, цілочисельність є обов’язковою частиною математичної постановки.

25.25. Підсумкова логіка вибору інструмента

Якщо модель переважно лінійна і містить суміш неперервних та цілих змінних, MILP є природним базовим вибором. Якщо всі ключові змінні цілі й модель насичена логічними умовами, призначеннями або розкладом, CP-SAT часто дає зручніший модельний інтерфейс.

В обох випадках результат завершується однаково: статус, допустимість, цілочисельність та повторне обчислення цілі.

25.26. Чому область цілих значень потрібно пояснювати предметно

Формальна цілочисельність має сенс тільки тоді, коли вона походить із реального рішення. Кількість машин є цілою, а обсяг пального може бути неперервним. Зайва цілочисельність ускладнює модель без користі, тому домен кожної змінної треба обґрунтувати.

25.27. Малий приклад як тест API чисельного розв’язувача

Задача з трьома проєктами має відомий оптимум 11. Вона зручна для перевірки налаштувань SciPy або CP-SAT. Якщо код повертає інший результат, спочатку треба перевірити знак цілі, бюджетне обмеження, межі змінних і цілочисельність. Лише після цього варто шукати проблему в налаштування чисельного розв’язувача.

25.28. Перевірка цілі після SciPy milp

SciPy мінімізує переданий вектор коефіцієнтів. У задачі максимізації ми передаємо \(-c\), тому result.fun має протилежний знак до предметної користі. Після чисельного розв’язувача потрібно повторно обчислити \(c^Tx\) з початковими додатними коефіцієнтами.

Ця перевірка одночасно контролює знак цілі та порядок компонентів вектора рішення.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

26. Підсумок

Цілочисельна та бінарна оптимізація додає до моделі дискретність. Змінні можуть означати кількість неподільних об’єктів, факт вибору, призначення або логічне рішення, тому дробове значення часто не має предметного змісту. Домен змінних відрізняє MILP і CP-SAT від неперервної лінійної оптимізації.

Після розв’язання перевіряють лінійні обмеження, а також цілочисельність або бінарність кожної відповідної змінної. Для бінарних рішень значення повинні бути узгоджені з логічним змістом моделі. Розв’язувач також може повернути інформацію про межі, розрив оптимальності та причину завершення, що важливо для великих задач.

Дискретність робить простір рішень складнішим, тому статус і сертифікат оптимальності потрібно читати уважно. Наступна лекція узагальнює цю дисципліну перевірки для різних класів оптимізаційних задач.