Целочисленное программирование: когда решения должны быть целыми

🎯 Зачем это нужно?

Представь: Netflix решает, какие сериалы покупать в следующем году 🎬. Нельзя купить “половину сериала” - либо покупаешь целиком, либо не покупаешь вообще. Или Amazon планирует, где построить склады 📦 - склад либо есть, либо его нет.

Обычная линейная оптимизация может дать ответ: “постройте 2.7 склада”. Но как построить 0.7 склада? 😅

Реальные кейсы:

• 🏭 Производство: Сколько станков купить (не можешь купить 3.14 станка)
• 📱 Uber: Как оптимально распределить водителей по районам города
• 🎮 Steam: Какие игры включить в бандл со скидкой
• 💰 Банки: Портфель кредитов (выдать кредит или нет - бинарное решение)

📚История вопроса

В 1958 году Ральф Гомори работал в IBM и столкнулся с задачей: как оптимально резать рулоны стали на заготовки нужного размера? 🔪 Отходы стоили компании миллионы долларов!

Проблема: классический симплекс-метод давал дробные решения типа “разрежьте 5.7 рулонов”. Гомори изобрел метод отсекающих плоскостей - первый алгоритм для целочисленного программирования.

Сегодня эти алгоритмы работают в логистике Amazon, планировании производства Tesla, и даже в составлении расписаний в школах! 📚

💡 Интуиция

Обычная оптимизация = поиск лучшей точки в непрерывном пространстве (можно “плыть” в любом направлении)

Целочисленная оптимизация = поиск среди дискретных точек (можно “прыгать” только по целым координатам)

[МЕДИА: image_01] Описание: Сравнение непрерывной и дискретной оптимизации на двумерной плоскости Промпт: “educational illustration showing continuous vs discrete optimization, grid of integer points, continuous feasible region shaded blue, discrete feasible points as red dots, optimal solutions marked, modern mathematical style”

Аналогия: Это как разница между:

• 🎯 Дартс (можно попасть в любую точку мишени)
• ♟️ Шахматы (можно ходить только по клеткам)

Казалось бы, просто округлить решение обычной задачи? НЕТ! ❌ Округленное решение может:

1. Нарушить ограничения
2. Быть далеко от оптимума
3. Вообще оказаться недопустимым

📐 Формальное определение

Задача целочисленного программирования (ILP):

minimize   c^T x
subject to Ax ≤ b
           x_i ∈ ℤ для всех i

Типы переменных:

• Бинарные: x_i ∈ {0,1} (да/нет решения)
• Целые: x_i ∈ ℤ (любые целые числа)
• Смешанные: часть переменных целые, часть непрерывные

LP-релаксация = та же задача, но без требования целочисленности:

minimize   c^T x
subject to Ax ≤ b
           x_i ≥ 0

🔍 Примеры с разбором

Пример 1: Задача о рюкзаке (Netflix покупает контент)

Netflix выбирает сериалы на год с бюджетом $100M:

Формулировка:

maximize   50x₁ + 30x₂ + 60x₃ + 35x₄
subject to 30x₁ + 20x₂ + 40x₃ + 25x₄ ≤ 100
           x_i ∈ {0,1}  (купить или не купить)

LP-релаксация: максимум при x₁=1, x₂=1, x₃=1, x₄=0.6 = 155 Целочисленное решение: x₁=1, x₂=1, x₃=1, x₄=0 = 140

[МЕДИА: image_02] Описание: Визуализация задачи о рюкзаке с сериалами Netflix Промпт: “knapsack problem visualization with Netflix series as items, budget constraint shown as knapsack capacity, profit vs cost scatter plot, binary decision variables highlighted, professional data visualization style”

Пример 2: Размещение серверов (Branch & Bound)

Яндекс решает, в каких из 3 городов разместить сервера:

• Фиксированная стоимость: Москва=50, СПб=40, Казань=30
• Покрытие пользователей: М=100, СПб=80, К=60
• Бюджет: 80

Решение методом ветвей и границ:

                    LP-релакс: 146.67
                   /              \
              x₁=0                   x₁=1
         LP: 133.33               LP: 120
        /         \              /        \
    x₂=0          x₂=1      x₂=0        x₂=1  
LP: 120       LP: 133.33   LP: 120    недопустимо
    |            |           |
   x₃=1        x₃=1        x₃=1
  120✓        133.33✓      120

Оптимум: Москва=НЕТ, СПб=ДА, Казань=ДА, прибыль=140

🎮 Практика

Базовый уровень 🟢

Задание 1: Компания производит столы (прибыль 100₽) и стулья (прибыль 60₽). На стол нужно 4 ед. древесины, на стул - 2 ед. Древесины 20 ед. Сколько производить?

Задание 2: Реши LP-релаксацию: max 3x₁ + 2x₂ при x₁ + 2x₂ ≤ 5, x₁,x₂ ≥ 0

Задание 3: Для предыдущей задачи найди оптимальное целочисленное решение перебором

Задание 4: Геймер покупает игры в Steam: Cyberpunk (500₽, 8/10), Witcher (300₽, 9/10), GTA (400₽, 7/10). Бюджет 700₽. Формулируй как ILP.

Продвинутый уровень 🟡

Задание 5: Докажи, что оптимум ILP всегда ≤ оптимума LP-релаксации

Задание 6: Построй дерево branch&bound для задачи: max 5x₁ + 3x₂ при 3x₁ + 2x₂ ≤ 12, x₁,x₂ ∈ {0,1,2,3,4}

Задание 7: Сформулируй задачу о назначении: 3 программиста на 3 проекта, каждый на один проект

Задание 8: Дана матрица эффективности 3×3. Найди оптимальное назначение венгерским методом

Челлендж 🔴

Задание 9: Проанализируй, почему задача коммивояжера NP-полная

Задание 10: Предложи эвристический алгоритм для большой задачи о рюкзаке (n>1000)

Задание 11: Реализуй простой branch&bound на Python для задачи из примера 2

⚠️ Частые ошибки

❌ Ошибка: “Просто округлю решение LP-релаксации” ✅ Правильно: Используй специальные алгоритмы (branch&bound, cutting planes) 💡 Почему: Округление может нарушить ограничения или дать плохое решение

❌ Ошибка: “ILP = обычная оптимизация, только переменные целые” ✅ Правильно: ILP принципиально сложнее (NP-полные задачи vs P) 💡 Почему: Даже проверка оптимальности решения может быть сложной

❌ Ошибка: “Если LP-релаксация дала целое решение, то это оптимум ILP” ✅ Правильно: Да, это верно! Такие случаи встречаются в специальных задачах 💡 Почему: Оптимум релаксации - верхняя граница для ILP

❌ Ошибка: “Branch&bound всегда быстрый” ✅ Правильно: В худшем случае - экспоненциальное время 💡 Почему: Может потребоваться перебор всех 2ⁿ комбинаций бинарных переменных

❌ Ошибка: “Эвристики не нужны, есть точные алгоритмы” ✅ Правильно: Для больших задач эвристики критически важны 💡 Почему: NP-полнота означает отсутствие быстрых точных алгоритмов

🎓 Главное запомнить

✅ Суть: Оптимизация с ограничением целочисленности переменных ✅ Ключевая связь: LP-релаксация дает верхнюю границу для задачи максимизации ✅ Применение: Логистика, планирование, размещение ресурсов, игровая индустрия

🔗 Связь с другими темами

Откуда пришли: Линейное программирование (урок 283) заложило основу - симплекс-метод и теория двойственности

Куда ведет:

• Комбинаторная оптимизация (задача коммивояжера, раскраска графов)
• Теория сложности вычислений (P vs NP)
• Machine Learning (feature selection, структурное обучение)
• Криптография (задачи на целочисленных решетках)

Связь с ML: В современном ML целочисленное программирование используется для:

• Отбора признаков (какие переменные включить в модель)
• Нейронной архитектурной оптимизации (Neural Architecture Search)
• Квантизации нейросетей (округление весов до целых значений)