В задаче 0–1 целочисленного программирования дан целочисленный набор линейных неравенств, и требуется определить, существует ли бинарный вектор \(x\in\{0,1\}^n\), удовлетворяющий им. В форме курса вход задаётся матрицей \(A\) и вектором \(b\), а условие имеет вид \(Ax^{T}\ge b^{T}\)
Задача NP-полна. Принадлежность \(NP\) следует из полиномиальной проверки заданного бинарного решения, а NP-трудность — из сведения SAT: каждой скобке КНФ сопоставляется одно линейное неравенство, истинное ровно тогда, когда скобка
Что важно запомнить
- Искомые переменные ограничены значениями 0 и 1.
- Проверка готового бинарного вектора выполняется за полиномиальное время, поэтому задача принадлежит \(NP\).
- В сведении SAT каждая скобка превращается в линейное
- Положительный литерал даёт коэффициент \(+1\), отрицательный — \(-1\). Свободная часть учитывает число отрицательных литералов.
Постановка задачи
Пусть дана целочисленная матрица \(A=(a_{ij})\) размера \(p\times n\) и целочисленный вектор \(b=(b_1,\ldots,b_p)\). Требуется установить, существует ли \(x\in\{0,1\}^n\), для которого \(Ax^{T}\ge b^{T}\)
Сведение SAT к 0–1 ЦП
Пусть \(K=C_1\wedge\cdots\wedge C_p\) — КНФ от переменных \(x_1,\ldots,x_n\). Для строки, соответствующей скобке \(C_i\), коэффициент при \(x_j\) выбирают так:
- \(a_{ij}=1\), если в \(C_i\) входит \(x_j\).
- \(a_{ij}=-1\), если в \(C_i\) входит \(\neg x_j\).
- \(a_{ij}=0\), если переменная в скобке отсутствует.
Если в \(C_i\) имеется \(r_i\) отрицательных литералов, полагают \(b_i=1-r_i\)
Для бинарного набора левая часть равна числу истинных положительных литералов минус число ложных отрицательных литералов. Неравенство \(\sum_j a_{ij}x_j\ge1-r_i\) выполняется тогда и только тогда, когда хотя бы один литерал скобки \(C_i\) истинен. Поэтому вся система имеет бинарное решение ровно тогда, когда исходная КНФ выполнима.
Матрица и вектор строятся за полиномиальное время и имеют полиномиальный размер. Следовательно, \(SAT\prec 0\text{-}1\text{ ЦП}\). Вместе с полиномиальной проверяемостью решения это даёт
Пример простыми словами
Скобке \(x_1\vee\neg x_2\vee x_3\) соответствует неравенство \(x_1-x_2+x_3\ge0\): здесь один отрицательный литерал, поэтому правая часть равна \(1-1=0\). Набор \((0,1,0)\) нарушает неравенство и действительно делает всю скобку ложной. Любой набор, делающий хотя бы один её литерал истинным, удовлетворяет неравенству.
Частые ошибки
- Смешивать decision problem с задачей оптимизации целевой функции. В доказательстве NP-полноты рассматривается вопрос существования бинарного допустимого решения.
- Забывать ограничение \(x_j\in\{0,1\}\). Без него получается другая задача.
- Перепутать знак коэффициента отрицательного литерала: для \(\neg x_j\) используется \(-1\), а изменение правой части компенсирует константу из \(1-x_j\).
