Целочисленное программирование 🔢

Реши задачу линейного программирования, округли ответ до ближайшего целого — и в большинстве реальных задач получишь либо недопустимое решение, либо решение, которое сильно проигрывает истинному оптимуму. Это не курьёз и не следствие невезения с конкретными числами. Как только в постановке задачи появляется требование «купи целое число серверов», «назначь ровно этого сотрудника на эту смену» или «выбери не более 12 признаков из 200», методы, которые ты изучал последние пять уроков — симплекс-метод, двойственность, условия Каруша — Куна — Таккера, методы активных множеств и внутренней точки для квадратичного программирования, — перестают напрямую работать. Все они опираются на то, что допустимое множество решений — выпуклое тело, гладкое и непрерывное, где можно скользить вдоль границы или двигаться внутрь по направлению убывания функции. Множество целых точек внутри многогранника такой структурой не обладает вообще.

Этот урок — про целочисленное программирование (ЦП): оптимизацию, в которой часть или все переменные обязаны принимать целые значения. Ты увидишь, почему допустимая область такой задачи — не выпуклое множество, а разрозненное облако точек с целыми координатами, почему это далеко не техническая деталь, а причина, по которой задача в общем случае становится NP-трудной — то есть для неё не существует известного алгоритма, гарантированно быстрого на любых входных данных. А затем разберём главный практический инструмент, который заставляет эту в теории безнадёжную задачу решаться на практике каждый день в тысячах логистических, финансовых и производственных систем — метод ветвей и границ, с полной пошаговой трассировкой на конкретном числовом примере, чтобы ты видел не общую идею, а буквально каждый шаг алгоритма.

Отдельное место в уроке займёт бинарное программирование — частный, но исключительно важный случай, где каждая переменная принимает значение 0 или 1 и кодирует бинарное решение «да/нет». На двух классических задачах, о рюкзаке и о назначениях, ты увидишь и типичный пример NP-трудной комбинаторной задачи, и редкий случай, когда специальная структура ограничений делает задачу полиномиально разрешимой без всякого перебора. А в конце мы явно и честно свяжем тему с машинным обучением: отбор признаков с фиксированным числом отбираемых переменных — это буквально задача бинарного целочисленного программирования, и некоторые формулировки поиска архитектур (AutoML/NAS) устроены точно так же.

Этот урок завершает подблок классической оптимизации с ограничениями — уроки 279–284, от условий оптимальности через линейное и квадратичное программирование до сегодняшней темы. Сразу после него курс делает содержательный поворот: с урока 285 начинается блок численных итеративных методов — градиентный спуск и его многочисленные модификации, — на которых в буквальном смысле обучается любая нейросеть, о которой ты когда-либо слышал.

История

Систематическая теория целочисленного программирования — заметно более молодая дисциплина, чем линейное программирование, хотя сами задачи с целочисленными неизвестными (диофантовы уравнения) математики решали ещё в античности. Первый настоящий прорыв в вычислительном подходе к целочисленной оптимизации сделал американский математик Ральф Гомори, работавший в конце 1950-х годов в Принстонском университете и затем в компании IBM. В 1958 году он предложил метод отсекающих плоскостей: если решение ЛП-релаксации оказывается нецелым, к задаче можно добавить дополнительное линейное неравенство — «отсечение», которое отрезает от многогранника найденную нецелую вершину, не отрезая при этом ни одной допустимой целой точки. Повторяя эту процедуру, можно постепенно «подрезать» многогранник до тех пор, пока его вершина не окажется целочисленной. Метод Гомори был первым алгоритмом, для которого вообще была доказана сходимость к точному целочисленному оптимуму за конечное число шагов — до этого у исследователей операций попросту не было строгого способа решать такие задачи, кроме полного перебора.

Почти одновременно, в 1960 году, британские исследователи Айлса Лэнд и Элисон Дойг предложили метод ветвей и границ — тот самый алгоритм, который станет центральной темой сегодняшнего урока. Идея оказалась настолько удачной, что довольно быстро обогнала по практической популярности метод одних только отсекающих плоскостей: вместо того чтобы пытаться «подрезать» многогранник до целочисленной формы, метод Лэнд — Дойг систематически разбивает исходную задачу на подзадачи с дополнительными ограничениями и отбрасывает те из них, которые заведомо не могут дать решение лучше уже найденного. Обрати внимание, что Элисон Дойг была совсем молодой исследовательницей на момент публикации — эта работа стала одной из считаных статей по исследованию операций той эпохи, написанных студенткой, и оказала влияние на всю последующую вычислительную комбинаторную оптимизацию.

Дальнейшая история — история сращивания обоих подходов. Современные промышленные решатели смешанного целочисленного программирования (CPLEX, Gurobi, SCIP, открытый CBC) реализуют гибридный алгоритм ветвей и отсечений (branch-and-cut): в каждом узле дерева ветвей и границ дополнительно генерируются отсекающие плоскости в духе Гомори, чтобы сузить релаксацию и ускорить поиск, прежде чем ветвиться дальше. Именно эта комбинация идей 1958 и 1960 годов лежит в основе решения задач авиационного планирования экипажей, логистической маршрутизации и производственного планирования, которые сегодня рутинно решаются для задач с миллионами переменных — притом что теоретически, в худшем случае, эти задачи остаются экспоненциально трудными.

Постановка задачи и почему она сложнее непрерывной

Интуиция

Возьми уже знакомую тебе по урокам 280–283 форму задачи линейного или квадратичного программирования и добавь всего одно дополнительное требование: часть переменных должна быть целыми числами. На первый взгляд это звучит как мелкая техническая деталь — подумаешь, ещё одно ограничение среди прочих. На практике это меняет саму природу задачи. Пока переменные непрерывны, допустимое множество — это выпуклый многогранник: сплошное, «заполненное» тело, внутри и на границе которого можно свободно перемещаться, и в котором любые две допустимые точки соединены отрезком из допустимых же точек. Как только к тем же самым ограничениям добавляется требование целочисленности, допустимое множество превращается в конечный (или счётный) набор изолированных точек — узлов решётки, лежащих внутри того же многогранника. Между двумя соседними допустимыми целыми точками, вообще говоря, нет ни одной другой допустимой точки — там просто дробные, недопустимые координаты. Симплекс-метод, метод внутренней точки, условия ККТ — вся эта машинерия предполагает, что можно двигаться вдоль границы допустимой области или по направлению антиградиента внутри неё. Для дискретного облака точек понятие «двигаться вдоль границы» попросту не определено.

Определение

Задача целочисленного линейного программирования (ЦЛП) в общем виде записывается как

$$\min_{x} c^\top x \quad \text{при } Ax \le b,\ x \ge 0,\ x_i \in \mathbb{Z} \text{ для всех } i \in I,$$

где $I$ — множество индексов переменных, обязанных быть целыми. Если $I$ включает все переменные задачи, говорят о чистом целочисленном программировании; если лишь часть — о смешанном целочисленном программировании (смешанное целочисленное программирование, СЦП); если каждая переменная из $I$ дополнительно ограничена множеством $\{0,1\}$ — о бинарном (булевом) целочисленном программировании, которому посвящён отдельный раздел этого урока. Множество $\{x \in \mathbb{R}^n : Ax \le b,\ x \ge 0\}$ без требования целочисленности называется ЛП-релаксацией задачи — именно оно и остаётся тем самым «удобным» выпуклым многогранником из прошлых уроков, а истинное допустимое множество целочисленной задачи — это пересечение ЛП-релаксации с решёткой целых точек $\mathbb{Z}^n$, которое выпуклым множеством не является почти никогда.

Примеры

Пример 1: почему округление не работает. Рассмотрим задачу $\max\, x_1 + 5x_2$ при ограничениях $x_1 + 10x_2 \le 20$, $x_1 \le 2$, $x_1, x_2 \ge 0$, с требованием, что обе переменные целые. Решим сперва ЛП-релаксацию: при $x_1 = 2$ первое ограничение даёт $x_2 \le 1{,}8$, а прирост целевой функции от увеличения $x_2$ (коэффициент 5) намного выгоднее прироста от $x_1$ (коэффициент 1), значит выгодно выжать $x_1$ и $x_2$ по максимуму — оптимум ЛП-релаксации находится в точке $(2;\ 1{,}8)$ со значением $z = 2 + 9 = 11$. Наивное округление до ближайших целых даёт $(2;\ 2)$ — но тогда $x_1 + 10x_2 = 2 + 20 = 22 > 20$, ограничение нарушено, решение недопустимо. Округление вниз даёт допустимую, но далёкую от оптимума точку $(2;\ 1)$ со значением $z = 7$. Переберём же все действительно целые допустимые точки: при $x_1 = 0$ имеем $x_2 \le 2$, $z = 10$; при $x_1 = 1$ имеем $x_2 \le 1$ (так как $10x_2 \le 19$ означает $x_2 \le 1{,}9$, а $x_2$ целое), $z = 1 + 5 = 6$; при $x_1 = 2$ имеем $x_2 \le 1$, $z = 2 + 5 = 7$. Истинный целочисленный оптимум — это $(0;\ 2)$ со значением $z = 10$, которое ни округление вверх, ни округление вниз от ЛП-решения даже не рассматривали как кандидата, потому что оно находится в совершенно другой вершине допустимой области.

Пример 2: дискретность допустимого множества. Возьмём тот же многогранник ЛП-релаксации из примера 1. Он представляет собой сплошную четырёхугольную область на плоскости $(x_1, x_2)$ с вершинами $(0;0)$, $(2;0)$, $(2;\,1{,}8)$ и $(0;\,2)$. Целочисленное же допустимое множество — это всего лишь семь отдельных точек внутри и на границе этого многоугольника: $(0;0)$, $(1;0)$, $(2;0)$, $(0;1)$, $(1;1)$, $(2;1)$ и $(0;2)$. Ни одна пара этих точек не соединена отрезком, целиком состоящим из допустимых точек с целыми координатами (между $(0;0)$ и $(2;0)$, например, лежит недопустимая с точки зрения целочисленности, но геометрически «промежуточная» точка $(1{,}3;\,0)$ — впрочем, она как раз целая по $x_2$; возьми вместо неё пару $(0;1)$ и $(2;0)$: середина отрезка — $(1;\,0{,}5)$, у которой $x_2$ дробная, значит середина недопустима). Понятие «выпуклая комбинация двух допустимых решений тоже допустима», на которое опирается вся теория выпуклой оптимизации, здесь попросту неверно.

Пример 3: производственное планирование с целыми станками. Компания решает, сколько станков типа A и типа B закупить для нового цеха, чтобы максимизировать прибыль при ограниченном бюджете и площади цеха. Пусть ЛП-релаксация даёт оптимум «2,7 станка типа A и 1,4 станка типа B». Число станков физически не может быть дробным — «2,7 станка» не означает ничего практического, в отличие от, скажем, задачи о смешивании сплавов из уроков по линейному программированию, где дробные доли компонентов вполне реальны. Округление здесь не просто снижает точность решения — оно может либо превысить бюджет (если округлить вверх), либо оставить неиспользованный ресурс, которым можно было распорядиться иначе (если округлить вниз), и ни один из этих исходов не гарантированно близок к истинно наилучшему целочисленному распределению закупок.

Почему это важно

Дискретность встречается в прикладных задачах машинного обучения и исследования операций гораздо чаще, чем кажется на первый взгляд: число серверов в облачной инфраструктуре, число выбираемых признаков, число открываемых складов, число назначаемых смен — всё это принципиально целочисленные величины, для которых непрерывный ответ либо бессмыслен, либо требует отдельного, нетривиального шага «превращения дробного решения в целое», причём этот шаг, как показал пример 1, может стоить существенной доли оптимальности. Понимание того, что допустимое множество целочисленной задачи не является выпуклым, — это не абстрактная математическая деталь, а прямое объяснение того, почему для таких задач нельзя просто взять симплекс-метод или метод внутренней точки и закончить на этом: нужен принципиально другой алгоритмический аппарат, к которому мы и переходим.

NP-трудность целочисленного программирования

Интуиция

Задача линейного программирования решается за полиномиальное время — методом эллипсоидов Хачияна (1979) или методами внутренней точки, которые ты видел в контексте квадратичного программирования. Добавление одного-единственного требования целочисленности к хотя бы одной переменной способно вывести задачу за пределы класса задач, для которых известен полиномиальный алгоритм. Причина — комбинаторный взрыв: как только решение нужно искать не на гладкой поверхности многогранника, а среди дискретных вариантов, число этих вариантов в общем случае растёт экспоненциально с числом переменных, и никакого известного «короткого пути», аналогичного движению вдоль градиента, для произвольной целочисленной задачи не существует.

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

NP-трудность общего целочисленного программирования. Задача проверки допустимости целочисленной линейной программы (существует ли вообще $x \in \mathbb{Z}^n$, удовлетворяющий $Ax \le b$) NP-полна в общем случае — это классический результат теории сложности вычислений. Отсюда следует, что и сама оптимизационная задача целочисленного программирования NP-трудна: если бы существовал алгоритм, решающий её за полиномиальное время при любых входных данных, он решал бы за полиномиальное время и любую NP-полную задачу распознавания, что означало бы $P = NP$ — до сих пор не доказанное и не опровергнутое утверждение, одна из семи задач тысячелетия.

Примеры

Пример 1: сведение задачи о сумме подмножества. Классическая NP-полная задача SUBSET-SUM формулируется так: дан набор целых чисел $a_1, \dots, a_n$ и число $b$ — существует ли подмножество этого набора, сумма которого равна ровно $b$? Она сводится к проверке допустимости целочисленной программы напрямую: введи бинарные переменные $x_i \in \{0,1\}$ и потребуй $\sum_i a_i x_i = b$. Ответ «да» на задачу о допустимости этой целочисленной системы равносилен ответу «да» на исходную задачу о сумме подмножества. Поскольку SUBSET-SUM NP-полна, а свести её к частному случаю целочисленного программирования удалось буквально в одну строчку ограничений, общая задача проверки допустимости целочисленных программ не может быть проще.

Пример 2: комбинаторный взрыв полного перебора. Для задачи 0/1-рюкзака с $n$ предметами полный перебор рассматривает $2^n$ возможных подмножеств. При $n = 10$ это 1024 варианта — компьютер перебирает их за долю секунды. При $n = 30$ это уже свыше миллиарда ($2^{30} \approx 1{,}07 \times 10^9$) вариантов — заметно, но ещё вычислимо. При $n = 50$ это свыше $10^{15}$ вариантов — уже недостижимо для полного перебора на любом реальном оборудовании в разумное время, а типичная промышленная задача целочисленного программирования содержит не десятки, а тысячи и десятки тысяч переменных.

n = 10:  2^n =                1 024
n = 20:  2^n =            1 048 576
n = 30:  2^n =        1 073 741 824
n = 50:  2^n =    1 125 899 906 842 624

Пример 3: асимметрия непрерывного и дискретного случая. Задача о назначениях (которую мы подробно разберём в разделе про бинарное программирование) формально тоже является задачей целочисленного, даже бинарного, программирования — но благодаря особой структуре матрицы ограничений (тотальной унимодулярности) её ЛП-релаксация автоматически даёт целочисленное решение, и задача решается за полиномиальное время специализированным венгерским алгоритмом. Это важный контрпример к поспешному выводу «раз это ЦП — значит, NP-трудная задача»: NP-трудность относится к общему случаю целочисленного программирования, а не к каждой конкретной задаче с целочисленными переменными — некоторые из них благодаря структуре остаются полиномиально разрешимыми, что мы подробно обсудим дальше.

Почему это важно

Осознание NP-трудности задачи — это не повод опустить руки, а прямое обоснование того, зачем вообще нужны такие алгоритмы, как метод ветвей и границ, эвристики и релаксации: если бы существовал быстрый точный метод для любой целочисленной задачи, весь следующий раздел урока был бы не нужен. На практике это означает конкретное инженерное решение: для небольших и умеренных по размеру задач (сотни-тысячи переменных с хорошей структурой) точные методы вроде метода ветвей и отсечений в современных решателях справляются за разумное время; для по-настоящему больших и плохо структурированных задач (как в некоторых постановках AutoML или крупномасштабной логистики) прибегают к эвристикам, метаэвристикам и приближённым релаксациям, сознательно жертвуя гарантией точного оптимума ради вычислимости за приемлемое время.

Релаксация линейного программирования как источник оценки

Интуиция

Раз саму целочисленную задачу решать напрямую трудно, разумный первый шаг — временно закрыть глаза на требование целочисленности и решить получившуюся ЛП-релаксацию, которая является задачей линейного программирования и решается быстро и надёжно методами из уроков 280–281. Ключевое наблюдение в том, что решение релаксации — это не просто «примерный», а строго обоснованный ориентир: поскольку допустимое множество целочисленной задачи является подмножеством допустимого множества релаксации (любая целая точка, удовлетворяющая ограничениям, — это по определению ещё и точка ЛП-многогранника, просто с дополнительным свойством целочисленности), оптимум над бо́льшим множеством не может быть хуже оптимума над его подмножеством.

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

Свойство границы релаксации. Пусть $z^*_{ЛП}$ — оптимальное значение ЛП-релаксации, а $z^*_{ЦП}$ — оптимальное значение исходной целочисленной задачи с той же целевой функцией и ограничениями. Тогда для задачи максимизации $z^*_{ЛП} \ge z^*_{ЦП}$ (релаксация даёт оценку сверху), а для задачи минимизации $z^*_{ЛП} \le z^*_{ЦП}$ (релаксация даёт оценку снизу). Разность $z^*_{ЛП} - z^*_{ЦП}$ (по модулю) называется интегральным разрывом (integrality gap) этой конкретной релаксации на этой конкретной задаче.

Примеры

Пример 1: численная оценка разрыва. В примере 1 предыдущего раздела ЛП-релаксация задачи о станках дала $z^*_{ЛП} = 11$, а истинный целочисленный оптимум оказался $z^*_{ЦП} = 10$. Интегральный разрыв здесь равен единице — небольшой, но ненулевой: даже до какого-либо перебора целых решений мы уже знаем, что лучше 11 в целочисленной постановке точно не будет, а значит, любое целое решение со значением, скажем, 10, можно с уверенностью признать как минимум очень близким к оптимальному, не продолжая поиск бесконечно.

Пример 2: нулевой разрыв в задаче о назначениях. Для задачи о назначениях (подробности — в следующем разделе) матрица ограничений обладает свойством тотальной унимодулярности — все её квадратные подматрицы имеют определитель $0$, $1$ или $-1$. Из классической теоремы линейного программирования следует, что в этом случае каждая вершина многогранника ЛП-релаксации автоматически имеет только целые координаты. Иными словами, решать ЛП-релаксацию симплекс-методом уже достаточно — она сама «случайно» выдаёт целочисленный ответ, интегральный разрыв равен нулю, и никакого ветвления не требуется вовсе.

Пример 3: дробная релаксация рюкзака как жадная оценка. Для задачи 0/1-рюкзака непрерывная (дробная) релаксация решается элементарно жадным алгоритмом: отсортируй предметы по убыванию отношения ценность/вес и заполняй рюкзак по порядку, беря последний предмет частично, если он не помещается целиком. Возьмём три предмета — $(v_1, w_1) = (10, 6)$, $(v_2, w_2) = (6, 5)$, $(v_3, w_3) = (4, 3)$ — и ёмкость рюкзака $8$. Отношения ценность/вес: $1{,}667$, $1{,}2$ и $1{,}333$ соответственно, порядок по убыванию: предмет 1, предмет 3, предмет 2. Берём предмет 1 целиком (вес 6, осталось 2 единицы ёмкости), затем предмет 3 частично — берём долю $2/3$ (весит ровно 2), давая вклад $4 \cdot 2/3 \approx 2{,}667$. Итоговая оценка релаксации: $z^*_{ЛП} = 10 + 2{,}667 = 12{,}667$ — верхняя граница, которую истинное целочисленное решение рюкзака превзойти не может.

Почему это важно

Релаксация — это не побочный вычислительный трюк, а именно тот механизм, который делает метод ветвей и границ практичным: вместо того чтобы полностью перебирать все целочисленные варианты в каждой подзадаче, алгоритм за одно быстрое решение ЛП получает достоверную границу и может целиком отбросить огромные поддеревья вариантов, если граница уже хуже уже найденного целочисленного решения. Без быстрой и надёжной оценки, которую даёт непрерывная релаксация, метод ветвей и границ выродился бы обратно в полный перебор.

Метод ветвей и границ

Интуиция

Представь дерево решений, в каждом узле которого стоит своя, чуть более ограниченная версия исходной задачи. В корне — исходная задача целиком. Решаем её ЛП-релаксацию: если решение оказалось целым — прекрасно, это готовый кандидат в оптимум, дальше исследовать эту ветвь незачем. Если решение дробное — выбираем одну дробную переменную, скажем $x_j = 2{,}5$, и «расщепляем» задачу на два дочерних узла: в одном добавляем ограничение $x_j \le 2$, в другом $x_j \ge 3$ — заметь, что ни одна допустимая целая точка при этом не теряется (целых значений между 2 и 3 попросту нет), а сама точка $2{,}5$ становится недопустимой в обеих дочерних задачах. Рекурсивно повторяем то же самое для каждого дочернего узла. Ключевая экономия по сравнению с полным перебором в том, что если ЛП-релаксация в каком-то узле уже даёт значение не лучше, чем лучшее уже найденное целое решение (рекорд), всё поддерево под этим узлом можно отбросить без исследования: даже наилучший возможный исход внутри этой ветви не сможет улучшить то, что уже есть. Это ровно та же идея, что отсечение альфа-бета в переборе игровых деревьев — не тратить время на заведомо бесперспективные направления поиска.

Алгоритм

Метод ветвей и границ для задачи максимизации $\max c^\top x$ при $Ax \le b$, $x \ge 0$, $x_i \in \mathbb{Z}$ для $i \in I$.

Шаг 1 (инициализация). Заведи очередь подзадач, изначально содержащую только исходную задачу. Установи текущий рекорд (лучшее найденное целое значение) равным $-\infty$, если ни одного целого решения ещё не найдено.

Шаг 2 (выбор узла). Извлеки из очереди одну подзадачу. Если очередь пуста — алгоритм завершён, рекорд является точным оптимумом.

Шаг 3 (решение релаксации). Реши ЛП-релаксацию этой подзадачи (без требования целочисленности).

Шаг 4 (отсечение по недопустимости). Если релаксация не имеет допустимых решений, отбрось этот узел целиком и вернись к шагу 2 — в этой ветви целых решений тоже быть не может.

Шаг 5 (отсечение по границе). Если оптимальное значение релаксации не превышает текущий рекорд, отбрось узел и вернись к шагу 2 — даже лучший случай в этой ветви не улучшит уже найденное решение.

Шаг 6 (отсечение по целочисленности). Если решение релаксации целиком целое, это допустимое решение исходной задачи. Если оно лучше рекорда — обнови рекорд этим значением, в любом случае отбрось узел (дальше ветвиться некуда) и вернись к шагу 2.

Шаг 7 (ветвление). Если ни одно из условий отсечения не выполнено, выбери переменную $x_j$, $j \in I$, с нецелым значением в решении релаксации, и добавь в очередь два новых узла: подзадачу с дополнительным ограничением $x_j \le \lfloor x_j \rfloor$ и подзадачу с ограничением $x_j \ge \lceil x_j \rceil$. Вернись к шагу 2.

Примеры

Пример 1: полная трассировка на конкретной задаче. Решим методом ветвей и границ задачу $\max\, 5x_1 + 4x_2$ при ограничениях $6x_1 + 4x_2 \le 24$, $x_1 + 2x_2 \le 6$, $x_1, x_2 \ge 0$, целые.

Корень. Решаем ЛП-релаксацию. Вершины многогранника: $(0;0)$ с $z=0$; $(4;0)$ (пересечение $6x_1+4x_2=24$ с осью $x_2=0$) с $z=20$; $(0;3)$ (пересечение $x_1+2x_2=6$ с осью $x_1=0$) с $z=12$; и пересечение обеих прямых, $(3;\,1{,}5)$, с $z = 15+6=21$. Оптимум релаксации — $(3;\,1{,}5)$, $z=21$. Переменная $x_2$ дробная — ветвимся по ней на $x_2 \le 1$ (узел A) и $x_2 \ge 2$ (узел B).

Узел A ($x_2 \le 1$). Решаем релаксацию с этим дополнительным ограничением. Проверка вершин показывает, что оптимум достигается на пересечении $6x_1+4x_2=24$ и $x_2=1$: отсюда $x_1 = 10/3 \approx 3{,}333$, $z = 5 \cdot 10/3 + 4 = 62/3 \approx 20{,}667$. Переменная $x_1$ дробная — ветвимся на $x_1 \le 3$ (узел A1) и $x_1 \ge 4$ (узел A2).

Узел A1 ($x_2 \le 1$, $x_1 \le 3$). Оптимум релаксации достигается в точке $(3; 1)$ (оба новых ограничения активны, при этом исходные ограничения задачи не нарушены: $6\cdot3+4\cdot1=22\le24$, $3+2=5\le6$), $z = 15+4=19$ — решение целое! Это первый найденный кандидат: рекорд $=19$, решение $(3;1)$.

Узел A2 ($x_2 \le 1$, $x_1 \ge 4$). Из ограничения $6x_1+4x_2\le24$ при $x_2\ge0$ следует $x_1\le4$, а вместе с $x_1\ge4$ это оставляет единственную точку $x_1=4$, откуда $4x_2\le0$, то есть $x_2=0$. Единственная допустимая точка узла — $(4;0)$, $z=20$ — решение целое и лучше предыдущего рекорда! Обновляем: рекорд $=20$, решение $(4;0)$.

Узел B ($x_2 \ge 2$). Решаем релаксацию: перебор вершин даёт $(0;2)$ с $z=8$, $(0;3)$ с $z=12$ и пересечение $x_1+2x_2=6$ с $x_2=2$ в точке $(2;2)$ с $z=18$ (проверка: $6\cdot2+4\cdot2=20\le24$ — допустимо). Оптимум узла B — $z=18$. Поскольку $18 \le 20 = $ рекорд, узел отсекается по границе — даже наилучший возможный исход в этой ветви (18) не превосходит уже найденное решение (20), и никакого дальнейшего ветвления по этой ветви не требуется.

Очередь подзадач пуста — алгоритм завершён. Оптимальное целочисленное решение: $x_1=4$, $x_2=0$, $z=20$.

Корень:  (3; 1,5),  z = 21   [x2 дробная]
├── A (x2≤1):  (3,333; 1),  z ≈ 20,667   [x1 дробная]
│    ├── A1 (x1≤3):  (3; 1),  z = 19   → целое, рекорд = 19
│    └── A2 (x1≥4):  (4; 0),  z = 20   → целое, рекорд = 20
└── B (x2≥2):  (2; 2),  z = 18 ≤ 20   → отсечение по границе

Пример 2: 0/1-рюкзак с несколькими типами отсечений. Три предмета из примера предыдущего раздела — $(v_1,w_1)=(10,6)$, $(v_2,w_2)=(6,5)$, $(v_3,w_3)=(4,3)$, ёмкость $8$, бинарные $x_1,x_2,x_3$. Дробная релаксация даёт $x_1=1$, $x_3=2/3$, $x_2=0$, $z\approx12{,}667$ — ветвимся по $x_3$.

Ветвь $x_3=0$. Максимизируем $10x_1+6x_2$ при $6x_1+5x_2\le8$, $x_1,x_2\in\{0,1\}$. Релаксация: $x_1=1$ (остаётся ёмкость 2), $x_2=2/5$ дробная, $z=12{,}4$ — ветвимся по $x_2$. При $x_2=0$: $x_1=1$ допустимо ($6\le8$), целое решение $z=10$. При $x_2=1$: остаётся ёмкость $3$, $6x_1\le3\Rightarrow x_1\le0{,}5$ дробная — ветвимся дальше: $x_1=1$ даёт вес $6+5=11>8$ — недопустимо, отсечение по недопустимости; $x_1=0$ даёт целое решение $z=6$. Лучшее в этой ветви — $z=10$ при $(1,0,0)$.

Ветвь $x_3=1$. Остаётся ёмкость $8-3=5$. Поскольку $x_1$ требует веса $6>5$, переменная $x_1=1$ уже недопустима при любом $x_2$ — вынужденно $x_1=0$. Тогда $5x_2\le5\Rightarrow x_2\le1$, берём $x_2=1$ (вес $5$, точно по ёмкости), суммарная ценность $4+6=10$. Решение $(0,1,1)$, $z=10$, вес $=8$.

Обе ветви дают одинаковый оптимум $z=10$, достигаемый на двух разных допустимых решениях — $(1,0,0)$ и $(0,1,1)$. Проверка полным перебором всех восьми подмножеств подтверждает: это действительно глобальный максимум ценности при ограничении по весу.

Пример 3: почему порядок ветвления и выбора узла важен. Одна и та же задача может решаться методом ветвей и границ за очень разное число исследованных узлов в зависимости от стратегии: в каком порядке выбирать узлы из очереди (поиск в глубину, поиск в ширину, «лучший сначала» — по значению релаксации) и какую именно дробную переменную выбирать для ветвления. Если в примере 1 первым исследовать узел B, а не узел A, придётся ветвиться и внутри узла B тоже, прежде чем найти в узле A решение $z=20$, которое отсекло бы узел B сразу. Хорошая эвристика выбора узла — «лучший сначала» по значению релаксации — стремится как можно раньше найти сильный рекорд именно для того, чтобы отсечение по границе начало работать максимально рано и на максимально большом числе узлов.

Почему это важно

Метод ветвей и границ — это не учебная абстракция, а буквально тот алгоритм (в паре с отсекающими плоскостями Гомори, вместе образующими метод ветвей и отсечений), который встроен в каждый промышленный решатель смешанного целочисленного программирования — CPLEX, Gurobi, SCIP, открытый CBC. В худшем случае число исследуемых узлов всё ещё может расти экспоненциально — теоретическая NP-трудность никуда не девается, — но качество релаксации, порядок ветвления и разумный рекорд на старте на практике сокращают реально исследуемое дерево на порядки по сравнению с полным перебором, и именно поэтому реальные задачи с тысячами переменных решаются за секунды, а не за геологическое время.

Бинарное программирование: рюкзак и задача о назначениях

Интуиция

Огромная доля прикладных задач целочисленного программирования сводится не к произвольным целым числам, а к чистому выбору «да или нет»: включить предмет в рюкзак или нет, назначить работника на задачу или нет, выбрать признак в модель или нет, открыть склад в этом городе или нет. Для таких решений естественная переменная — бинарная, $x_i \in \{0, 1\}$, где единица кодирует утвердительный выбор, а ноль — отрицательный. Формально это тот же самый частный случай целочисленного программирования из определения в начале урока, только с дополнительным верхним ограничением $x_i \le 1$ — но именно эта простая структура порождает целый пласт классических задач, часть из которых остаётся NP-трудной, а часть, как ты уже видел на примере задачи о назначениях, неожиданно решается за полиномиальное время.

Определение

Задача бинарного (0/1) программирования — это частный случай целочисленного программирования вида

$$\max \text{ (или } \min\text{) } c^\top x \quad \text{при } Ax \le b,\ x_i \in \{0, 1\} \text{ для всех } i.$$

Классические примеры — задача о рюкзаке: дан набор предметов с ценностями $v_i$ и весами $w_i$, требуется выбрать подмножество максимальной суммарной ценности с суммарным весом не выше ёмкости $W$, то есть $\max \sum_i v_i x_i$ при $\sum_i w_i x_i \le W$; и задача о назначениях: дана матрица затрат $c_{ij}$ на назначение исполнителя $i$ на задачу $j$, требуется назначить каждого исполнителя ровно на одну задачу и каждую задачу — ровно одному исполнителю, минимизируя суммарные затраты, то есть $\min \sum_{i,j} c_{ij} x_{ij}$ при $\sum_j x_{ij} = 1$ для каждого $i$, $\sum_i x_{ij} = 1$ для каждого $j$.

Примеры

Пример 1: 0/1-рюкзак — уже разобранная NP-трудная задача. Задача о рюкзаке из предыдущего раздела — канонический пример NP-трудной бинарной задачи: не существует известного алгоритма с полиномиальным временем работы относительно длины входа в худшем случае, хотя существует псевдополиномиальный алгоритм динамического программирования со сложностью $O(nW)$, эффективный, пока ёмкость $W$ не астрономически велика. Метод ветвей и границ, разобранный в примере 2 предыдущего раздела, — один из точных подходов к рюкзаку при произвольных, в том числе очень больших, значениях ёмкости.

Пример 2: задача о назначениях — полиномиально разрешимый частный случай. Рассмотрим матрицу затрат для трёх работников и трёх задач:

        T1   T2   T3
  W1:    9    2    7
  W2:    6    4    3
  W3:    5    8    1

Полный перебор всех $3! = 6$ перестановок назначений даёт суммарные затраты: $(W1{\to}T1, W2{\to}T2, W3{\to}T3) = 9+4+1=14$; $(W1{\to}T1, W2{\to}T3, W3{\to}T2) = 9+3+8=20$; $(W1{\to}T2, W2{\to}T1, W3{\to}T3) = 2+6+1=9$; $(W1{\to}T2, W2{\to}T3, W3{\to}T1) = 2+3+5=10$; $(W1{\to}T3, W2{\to}T1, W3{\to}T2) = 7+6+8=21$; $(W1{\to}T3, W2{\to}T2, W3{\to}T1) = 7+4+5=16$. Минимум — $9$, при назначении $W1{\to}T2$, $W2{\to}T1$, $W3{\to}T3$. Как уже обсуждалось в разделе про релаксацию, благодаря тотальной унимодулярности матрицы ограничений ЛП-релаксация этой задачи автоматически даёт этот же целочисленный ответ без всякого ветвления — на практике задачу решают ещё быстрее специализированным венгерским алгоритмом за полиномиальное время $O(n^3)$.

Пример 3: отбор признаков с фиксированным числом — реальная задача бинарного программирования. Пусть у тебя есть пять признаков с индивидуальными оценками информативности (например, взаимной информацией с целевой переменной): $f_1=0{,}42$, $f_2=0{,}35$, $f_3=0{,}51$, $f_4=0{,}20$, $f_5=0{,}30$, и нужно выбрать ровно $k=2$ признака, максимизируя суммарную информативность: $\max \sum_i s_i x_i$ при $\sum_i x_i = 2$, $x_i \in \{0,1\}$. Без учёта взаимодействий между признаками эта задача тривиальна — просто бери два признака с наибольшим индивидуальным баллом, $f_3$ и $f_1$, суммарно $0{,}93$. Но добавим реалистичную деталь: признаки $f_1$ и $f_3$ сильно коррелируют между собой, и их совместный выбор добавляет штраф $-0{,}30$ за избыточность (одна и та же информация учитывается дважды). Полный перебор всех $\binom{5}{2}=10$ пар с учётом этого штрафа даёт максимум на паре $(f_2, f_3)$ со значением $0{,}35+0{,}51=0{,}86$, тогда как «жадная» пара $(f_1, f_3)$ с учётом штрафа даёт лишь $0{,}42+0{,}51-0{,}30=0{,}63$ — заметно хуже. Как только в целевой функции появляется взаимодействие между переменными, простая сортировка по индивидуальному баллу перестаёт быть надёжной, и задача становится настоящей задачей бинарного (в данном случае квадратичного бинарного) программирования, требующей явного комбинаторного поиска или решения соответствующей ЦП-формулировки решателем.

Почему это важно

Бинарное программирование — это ровно тот математический язык, на котором формулируются задачи выбора с фиксированным бюджетом: сколько предметов взять при ограниченной ёмкости, кого назначить куда при ограниченных ресурсах, какие признаки оставить при ограничении на их число. В машинном обучении отбор признаков с точным ограничением «оставить ровно $k$ признаков из $n$» — это буквально задача бинарного целочисленного программирования $\max \sum_i s_i x_i$ (или более сложная целевая функция с учётом взаимодействий между признаками) при $\sum_i x_i = k$, $x_i \in \{0,1\}$, как показано в примере 3 — и при $n$ в сотни признаков полный перебор всех $\binom{n}{k}$ подмножеств быстро становится нереалистичным, так что на практике используют именно методы целочисленного программирования (или их эвристические приближения) вместо наивной сортировки по важности. Аналогично устроены некоторые формулировки поиска архитектур в AutoML (NAS, поиск архитектур нейросетей): выбор дискретного гиперпараметра — числа слоёв сети, типа операции на каждом слое (свёртка $3\times3$, свёртка $5\times5$, пулинг) — естественно моделируется бинарными индикаторными переменными с ограничением «на каждом слое выбрана ровно одна операция», что превращает задачу выбора архитектуры в задачу целочисленного программирования колоссального размера, решаемую на практике не точным методом ветвей и границ, а эвристиками, обучением с подкреплением или дифференцируемыми релаксациями вроде DARTS, которые по сути аппроксимируют именно эту дискретную комбинаторную структуру непрерывной.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Дай определение задачи целочисленного линейного программирования в общем виде и укажи её главное отличие от чисто линейного программирования.

Задание 2: Реши ЛП-релаксацию задачи $\max\, x_1+5x_2$ при $x_1+10x_2\le20$, $x_1\le2$, $x_1,x_2\ge0$ (без требования целочисленности).

Задание 3: Для той же задачи найди истинный целочисленный оптимум перебором целых точек при $x_1\in\{0,1,2\}$.

Задание 4: Объясни, почему округление ЛП-решения $(2;\,1{,}8)$ до $(2;2)$ даёт недопустимое решение.

Задание 5: Верно ли, что допустимая область целочисленной задачи является выпуклым множеством? Обоснуй.

Задание 6: Сформулируй в общем виде задачу бинарного (0/1) программирования и укажи, чем она отличается от общего целочисленного программирования.

Задание 7: Является ли ЛП-релаксация верхней или нижней оценкой оптимума в задаче максимизации? А в задаче минимизации?

Задание 8: В задаче максимизации узел метода ветвей и границ имеет ЛП-оптимум $z=15$, а текущий рекорд равен $z=18$. Нужно ли ветвить этот узел дальше?

Задание 9: Для 0/1-рюкзака существует псевдополиномиальный алгоритм динамического программирования. Не противоречит ли это утверждению об NP-трудности рюкзака?

Задание 10: Чем задача о назначениях отличается от общей задачи целочисленного программирования с точки зрения вычислительной сложности?

Средние задания (11–20)

Задание 11: Реши ЛП-релаксацию корневого узла задачи $\max\,5x_1+4x_2$ при $6x_1+4x_2\le24$, $x_1+2x_2\le6$, $x_1,x_2\ge0$ и укажи, по какой переменной нужно ветвиться.

Задание 12: Сформулируй ограничения двух дочерних узлов при ветвлении по $x_2=1{,}5$ из предыдущего задания.

Задание 13: Реши ЛП-релаксацию узла A ($x_2\le1$) и определи, нужно ли ветвиться дальше.

Задание 14: Реши узел A1 ($x_2\le1$, $x_1\le3$) и проверь целочисленность решения.

Задание 15: Реши узел A2 ($x_2\le1$, $x_1\ge4$) и сравни с рекордом из задания 14.

Задание 16: Реши узел B ($x_2\ge2$) и реши, нужно ли исследовать его дальше при текущем рекорде $=20$.

Задание 17: Укажи финальный оптимум задачи из заданий 11–16 и проверь его полным перебором целых точек допустимой области.

Задание 18: Для рюкзака с предметами $(v,w)$: $(10,6)$, $(6,5)$, $(4,3)$ и ёмкостью $8$ вычисли значение жадной (дробной) ЛП-релаксации и укажи, какая переменная получилась дробной.

Задание 19: Ветвясь по $x_3=0$ из задания 18, найди оптимальное целочисленное решение получившейся подзадачи (предметы 1 и 2, ёмкость 8).

Задание 20: Ветвясь по $x_3=1$ из задания 18, найди оптимум оставшейся подзадачи (ёмкость уменьшена на вес предмета 3) и сравни с результатом задания 19.

Продвинутые задания (21–30)

Задание 21: Запиши задачу выбора ровно $k=2$ признаков из 5 с максимизацией суммарной информативности в виде формальной задачи бинарного программирования.

Задание 22: Для оценок $s_1=0{,}42$, $s_2=0{,}35$, $s_3=0{,}51$, $s_4=0{,}20$, $s_5=0{,}30$ (без взаимодействий между признаками) найди оптимальный выбор $k=2$ простым сравнением.

Задание 23: Добавь штраф $-0{,}30$ за одновременный выбор $f_1$ и $f_3$ (сильная корреляция) и найди истинный оптимум полным перебором всех $\binom{5}{2}=10$ пар.

Задание 24: Объясни, почему задание 23 показывает, что отбор признаков с ограничением на их число и учётом взаимодействий — настоящая задача целочисленного программирования, а не просто сортировка.

Задание 25: Для матрицы затрат задачи о назначениях $3\times3$ из примера урока (W1: 9,2,7; W2: 6,4,3; W3: 5,8,1) проверь перебором всех шести перестановок, что минимальная стоимость равна 9.

Задание 26: Почему для задачи о назначениях не требуется метод ветвей и границ, хотя формально это тоже задача бинарного программирования?

Задание 27: Оцени число вершин дерева полного перебора для бинарной задачи с $n=20$ переменными и сравни с типичным числом узлов, реально исследуемых методом ветвей и границ.

Задание 28: В контексте AutoML/NAS объясни, как выбор дискретного гиперпараметра «число слоёв» и «тип операции на слое» можно смоделировать бинарными переменными.

Задание 29: Чем интегральный разрыв ЛП-релаксации отличается для задачи о назначениях и для задачи о рюкзаке? Что это значит для качества оценки в корневом узле метода ветвей и границ?

Задание 30: Перечисли три причины, по которым целочисленное программирование существенно сложнее вычислительно, чем линейное или квадратичное программирование с непрерывными переменными.

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

Ошибка 1. Считают, что «решить ЛП-релаксацию и округлить ответ» равносильно решению целочисленной задачи.

Как выглядит: «оптимум непрерывной задачи $(2;\,1{,}8)$, значит целочисленный ответ — примерно $(2;2)$».

Почему возникает: округление кажется естественным и дешёвым способом «доделать» уже готовое непрерывное решение.

Как правильно: округление может дать как недопустимое решение (нарушающее ограничения), так и допустимое, но далёкое от истинного оптимума — нужно либо решать задачу целочисленными методами (ветви и границы, отсекающие плоскости), либо, если размер задачи позволяет, честно перебирать целые кандидаты рядом с решением релаксации.

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

Как выглядит: «это же почти обычная задача ЛП, просто с одним целым числом — наверняка решается так же быстро».

Почему возникает: формулировка задачи меняется минимально, и кажется, что сложность решения должна меняться пропорционально минимально.

Как правильно: NP-трудность целочисленного программирования — свойство общего случая задачи, а не количества целочисленных переменных; даже одна целая переменная в невыгодной структуре ограничений способна сделать задачу вычислительно трудной, хотя, конечно, чем меньше целочисленных переменных, тем на практике обычно проще.

Ошибка 3. Путают направление оценки, которое даёт релаксация, — используют её как нижнюю границу в задаче максимизации или как верхнюю в задаче минимизации.

Как выглядит: «релаксация дала 11, значит целочисленный оптимум точно не меньше 11» в задаче максимизации.

Почему возникает: не всегда сразу очевидно, что допустимое множество ЦП — подмножество допустимого множества ЛП, а не наоборот.

Как правильно: поскольку каждое допустимое целое решение — это ещё и допустимая точка релаксации, оптимум релаксации не может быть хуже оптимума ЦП: в задаче максимизации это оценка сверху, в задаче минимизации — оценка снизу, и перепутать направление означает сделать в корне неверный вывод о качестве найденного решения.

Ошибка 4. При ветвлении по дробной переменной исследуют только одну из двух дочерних веток, интуитивно кажущуюся более перспективной, пропуская вторую.

Как выглядит: «переменная получилась равна 3,3, скорее всего ответ близок к 3 — сразу продолжим с $x_j\le3$ и не будем проверять $x_j\ge4$».

Почему возникает: кажется избыточным исследовать «явно менее вероятную» ветвь, особенно вручную.

Как правильно: метод ветвей и границ гарантирует нахождение точного оптимума только при полном (пусть и сокращённом отсечениями) переборе обеих дочерних ветвей в каждом узле — как показал пример с узлом A2 в главном разбираемом примере урока, именно «менее очевидная» ветвь ($x_1\ge4$) дала лучшее решение, чем более интуитивная ($x_1\le3$).

Ошибка 5. Считают, что метод ветвей и границ гарантированно исследует меньше узлов, чем полный перебор, при любой стратегии выбора узла и переменной для ветвления.

Как выглядит: «мы же используем ветви и границы, значит автоматически быстрее полного перебора, независимо от того, как реализован алгоритм».

Почему возникает: название метода звучит как гарантия эффективности сама по себе.

Как правильно: реальная эффективность сильно зависит от порядка исследования узлов и выбора переменной для ветвления — при неудачном порядке (например, откладывании исследования веток с сильным рекордом) отсечение по границе срабатывает поздно, и в худшем случае число исследованных узлов всё ещё может расти экспоненциально; именно поэтому промышленные решатели тратят значительные усилия на эвристики выбора узла и переменной.

Ошибка 6. Считают бинарное программирование принципиально другим методом, требующим отдельной от общего целочисленного программирования теории.

Как выглядит: «это же задача о рюкзаке, тут нужен какой-то свой особый алгоритм, а не то же самое, что в общем ЦП».

Почему возникает: классические задачи (рюкзак, назначения, покрытие множества) традиционно изучаются как отдельные именованные задачи со своей историей и специализированными алгоритмами.

Как правильно: бинарное программирование — это ровно тот же общий формализм целочисленного линейного программирования с дополнительным ограничением $x_i \in \{0,1\}$; метод ветвей и границ, релаксация, отсечение по границе применяются к нему без каких-либо изменений, а специализированные алгоритмы (динамическое программирование для рюкзака, венгерский алгоритм для назначений) — это дополнительные, более быстрые инструменты для конкретных структур, а не замена общей теории.

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

• Целочисленное программирование — это задача оптимизации с требованием, чтобы часть или все переменные принимали целые значения; допустимое множество такой задачи — дискретный набор точек, а не выпуклый многогранник.

• Наивное округление решения непрерывной релаксации может дать как недопустимое, так и допустимое, но далёкое от истинного оптимума решение — округление не является методом решения целочисленной задачи.

• Общее целочисленное программирование NP-трудно: не существует известного алгоритма с полиномиальным временем работы в худшем случае, что строго доказывается сведением к NP-полным задачам вроде SUBSET-SUM.

• ЛП-релаксация (снятие требования целочисленности) даёт достоверную оценку оптимума: верхнюю границу в задаче максимизации и нижнюю в задаче минимизации, поскольку допустимое множество ЦП — подмножество допустимого множества ЛП.

• Метод ветвей и границ (Ленд и Дойг, 1960) систематически разбивает задачу на подзадачи, решая релаксацию в каждом узле и отсекая ветви по трём причинам: недопустимость релаксации, значение релаксации не лучше текущего рекорда, или целочисленность найденного решения релаксации.

• Полная трассировка на конкретном примере ($\max\,5x_1+4x_2$) показывает все три типа отсечения на практике: узел B отсечён по границе ($18\le20$), узлы A1 и A2 дали целые решения (рекорд обновлялся дважды), а финальный оптимум $x_1=4,x_2=0,z=20$ найден без полного перебора всех целых точек.

• Бинарное программирование — частный случай целочисленного программирования с $x_i \in \{0,1\}$; задача о рюкзаке — классический NP-трудный пример, задача о назначениях благодаря тотальной унимодулярности матрицы ограничений решается за полиномиальное время без всякого ветвления.

• Отбор признаков с точным ограничением на их число — буквально задача бинарного целочисленного программирования; как только между признаками появляются взаимодействия (корреляция, избыточность), жадная сортировка по индивидуальной важности перестаёт быть оптимальной.

• Метод отсекающих плоскостей Гомори (1958) и метод ветвей и границ (1960), объединённые в современный алгоритм ветвей и отсечений, лежат в основе всех промышленных решателей смешанного целочисленного программирования — CPLEX, Gurobi, SCIP, CBC.

• Дискретные гиперпараметры в AutoML и поиске архитектур (число слоёв, тип операции) моделируются целочисленными/бинарными переменными; из-за колоссального размера таких задач на практике их решают эвристиками и дифференцируемыми релаксациями, а не точным перебором.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок опирается на весь пройденный подблок структурированной непрерывной оптимизации. Линейное программирование и симплекс-метод (уроки 280–281) дают тот самый быстрый способ решать ЛП-релаксацию в каждом узле метода ветвей и границ. Двойственность (урок 282) объясняет, почему оценка, которую даёт релаксация, — не случайное совпадение, а строгое математическое следствие соотношения между допустимыми множествами прямой задачи и её ослабленной версии. Квадратичное программирование (урок 283) показало, как непрерывная структура ограничений при выпуклой целевой функции гарантирует единственный глобальный оптимум, — и по контрасту с сегодняшним уроком ты видишь, что именно требование целочисленности, а не форма целевой функции, оказывается главным источником вычислительной трудности.

Что изучить дальше

Урок 285 открывает принципиально другой раздел курса — блок численных итеративных методов, начинающийся с градиентного спуска. Обрати внимание на смену масштаба: уроки 279–284 были посвящены задачам с явной, аналитически описываемой структурой ограничений — линейными неравенствами, квадратичными формами, требованием целочисленности, — которые решаются точными методами за конечное (пусть иногда и экспоненциальное) число шагов. Начиная с градиентного спуска, курс переходит к задачам, где явную структуру решения выписать невозможно в принципе — функция потерь нейросети с миллионами параметров не раскладывается ни на линейные, ни на квадратичные, ни тем более на целочисленные ограничения, — и вместо точного решения за конечное число шагов используются итеративные приближения, постепенно, шаг за шагом, спускающиеся к минимуму.

Где это нужно в жизни

🧮 Отбор признаков (отбор признаков). Задача «выбрать ровно $k$ признаков из $n$, максимизируя качество модели» с учётом взаимодействий между признаками — это прямая задача бинарного целочисленного программирования, как разобрано в примере с корреляцией признаков $f_1$ и $f_3$; на практике для умеренного числа признаков её решают точными или приближёнными ЦП-методами вместо наивной сортировки по важности.

🏗️ AutoML и поиск архитектур. Выбор дискретных гиперпараметров — числа слоёв, типа операции на каждом слое нейросети — естественно моделируется целочисленными переменными; некоторые исследовательские формулировки NAS напрямую решаются как задачи целочисленного (или смешанного целочисленного) программирования, хотя на практике из-за огромного размера пространства поиска чаще применяются эвристики и дифференцируемые релаксации.

📦 Классическое исследование операций. Планирование маршрутов доставки, назначение экипажей на авиарейсы, размещение складов с целочисленным числом единиц оборудования — область, в которой метод ветвей и границ и его современные развития остаются рабочим инструментом ежедневного индустриального масштаба, часто на задачах с десятками и сотнями тысяч переменных.

🎓 Итог подблока классической оптимизации (279–284). Шесть уроков назад блок начался с условий Каруша — Куна — Таккера (урок 279) — общего критерия оптимальности при ограничениях. Дальше ты последовательно увидел, как этот критерий специализируется для линейных ограничений и линейной цели (линейное программирование и симплекс-метод, 280–281), как задача смотрит на саму себя через двойственность (282), как выпуклая квадратичная цель меняет геометрию решения (квадратичное программирование, 283), и, наконец, сегодня — что происходит, когда к любой из этих структур добавляется требование целочисленности (284). Общая нить всего подблока — то, что структура ограничений и целевой функции определяет, какой именно инструмент решает задачу быстро и точно: симплекс-метод для линейных ограничений, методы активных множеств и внутренней точки для квадратичной цели, метод ветвей и границ для целочисленности. Это была последовательная, аналитически прозрачная часть теории оптимизации — впереди курс переходит туда, где такой явной аналитической структуры больше не будет, и придётся спускаться к минимуму итеративно, шаг за шагом, начиная с самого фундаментального из всех итеративных методов.

Интересные факты

• Ральф Гомори, автор метода отсекающих плоскостей 1958 года, проработал большую часть карьеры в IBM, а затем возглавлял фонд Alfred P. Sloan Foundation — редкий пример математика-исследователя, чей теоретический результат полувековой давности сегодня буквально каждый день работает внутри коммерческих решателей вроде CPLEX и Gurobi.

• Метод ветвей и границ предложили в 1960 году Айлса Лэнд и Элисон Дойг — на момент публикации Дойг была совсем молодой исследовательницей, а сама статья стала одной из самых влиятельных работ в истории исследования операций, определивших облик всей последующей вычислительной комбинаторной оптимизации.

• Современные промышленные решатели используют гибридный алгоритм ветвей и отсечений — метод ветвей и границ, в каждом узле которого дополнительно генерируются отсекающие плоскости Гомори (и их более современные развития вроде неравенств покрытия), что позволяет решать задачи с миллионами переменных, хотя теоретически в худшем случае задача остаётся экспоненциально трудной.

• Вопрос о том, существует ли вообще полиномиальный алгоритм для NP-трудных задач вроде общего целочисленного программирования, — это в точности вопрос $P$ против $NP$, одна из семи задач тысячелетия с призовым фондом в миллион долларов от института Клэя; доказательство или опровержение равенства этих классов сложности немедленно ответило бы и на вопрос о принципиальной разрешимости целочисленного программирования за полиномиальное время.

Лайфхаки

• Прежде чем браться за метод ветвей и границ или запускать тяжёлый решатель, всегда сначала реши ЛП-релаксацию — это быстро и почти бесплатно даёт границу, по которой можно сразу понять, насколько велик потенциальный интегральный разрыв и стоит ли вообще ожидать заметной разницы между непрерывным и целочисленным ответом.

• Если переменные модели кодируют решения «да/нет», формулируй их сразу как бинарные ($x_i \in \{0,1\}$), а не как общие целые с границами $[0,1]$ — многие решатели используют специализированные, более быстрые техники именно для явно бинарных переменных.

• Для реальных задач не пиши метод ветвей и границ с нуля — пользуйся готовыми решателями (PuLP, Google OR-Tools, SciPy milp, открытый CBC, коммерческие CPLEX и Gurobi), которые уже реализуют метод ветвей и отсечений с десятилетиями инженерной оптимизации внутри.

• Перед запуском точного решателя на большой задаче попробуй быстро получить хорошее допустимое целое решение любой жадной эвристикой и передать его решателю как стартовый рекорд («тёплый старт») — чем раньше в дереве появится сильный рекорд, тем раньше и активнее начнёт работать отсечение по границе.

• Прежде чем отбирать признаки жадной сортировкой по индивидуальной важности, проверь, есть ли в данных сильно коррелирующие признаки — если да, задача перестаёт быть сепарабельной и жадный выбор больше не гарантирует оптимума, как показал пример с признаками $f_1$ и $f_3$.

• Если задача, которую ты решаешь, похожа по структуре на транспортную задачу или задачу о назначениях (потоковые ограничения вида «сумма по строке равна 1, сумма по столбцу равна 1»), сначала проверь, не является ли матрица ограничений тотально унимодулярной — если да, можно сэкономить весь аппарат ветвей и границ и просто решить ЛП-релаксацию напрямую.

Целочисленное программирование закрывает подблок классической, аналитически прозрачной оптимизации с ограничениями — от условий Каруша — Куна — Таккера через симплекс-метод и двойственность до квадратичных и, наконец, целочисленных задач. Ты увидел, как явная структура ограничений — линейная, квадратичная, дискретная — определяет, какой именно точный метод решает задачу быстро и надёжно, и что происходит, когда эта структура становится настолько жёсткой (целочисленность), что даже теоретически быстрого алгоритма может не существовать. Дальше курс делает поворот: с урока 285 ты встретишься с градиентным спуском — методом, у которого нет ни симплекс-таблиц, ни дерева ветвлений, ни отсечений по границе, а есть только повторяющийся маленький шаг в сторону убывания функции. Именно этот скромный на вид итеративный шаг, повторённый миллионы раз, обучает сегодня каждую нейросеть, о которой ты слышал в новостях — и разбираться в том, как и почему он работает, ты начнёшь уже в следующем уроке.