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

Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны.

Целочисленное программирование является NP-трудной задачей. Частный случай 0-1 целочисленного линейного программирования, в котором переменные принимают значения только 0 или 1, является одной из 21 NP-полных задач Карпа.

Каноническая и стандартная виды ЦЛП

Задача целочисленного линейного программирования в каноническом виде выражается как

максимизировать	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
при условиях	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
и	$\mathbf {x} \in \mathbb {Z} ^{n}$,

а в стандартном виде

максимизировать	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
при условиях	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
и	$\mathbf {x} \in \mathbb {Z} ^{n}$

где $\mathbf {c} ,\mathbf {b}$ — векторы, а $A$ — матрица, все элементы которых являются целыми числами. Заметьте, что, как и в случае линейного программирования, ЦЛП-задача, не находящаяся в стандартном виде, может быть приведена к стандартному виду путём исключения неравенств введением дополнительных и искусственных переменных и заменой переменных, на которые не наложено ограничение неотрицательности, двумя переменными.

Пример

Целочисленный многогранник с линейным ослаблением

Рисунок справа показывает следующую задачу.

${\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\geq 0\\x,y&\in \mathbb {Z} \end{aligned}}$

Допустимые целые точки показаны красным и красные пунктирные линии показывают выпуклую оболочку этих точек, которая является наименьшим многоугольником, содержащим все эти точки. Синие линии вместе с координатными осями определяют многоугольник линейного ослабления, который задаётся неравенствами без требования целочисленности. Цель оптимизации — сдвинуть чёрную пунктирную линию так, чтобы она была как можно выше, но касалась многоугольника. Оптимальные решения целочисленной задачи — точки $(1,2)$ и $(2,2)$, на которых целевая функция принимает значение 2. Единственное решение ослабленной (линейной) задачи — точка $(1.8,2.8)$, в которой целевая функция принимает значение 2.8. Заметим, что если мы округлим решение задачи линейного программирования до ближайших целых, решение будет недопустимо для ЦЛП.

Доказательство NP-трудности

Следующее рассуждение является сведением задачи минимизации вершинного покрытия к задаче целочисленного программирования, что доказывает NP-трудность.

Пусть $G=(V,E)$ — неориентированный граф. Определим задачу линейного программирования следующим образом:

${\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\geq 0&&\forall v\in V\\y_{v}&\in \mathbb {Z} &&\forall v\in V\end{aligned}}$

Если наложить требование, чтобы $y_{v}$ принимали значения 0 или 1, любое допустимое решение для целочисленного программирования является подмножеством вершин. Из первого ограничения следует, что по меньшей мере один конец каждого ребра включен в подмножество. Таким образом, решение даёт покрытие вершин. Кроме того, если задано вершинное покрытие C, $y_{v}$ можно присвоить значение 1 для любого $v\in C$ и 0 для любого $v\not \in C$, что даёт нам допустимое решение задачи целочисленного программирования. Отсюда мы может заключить, что при минимизации суммы $y_{v}$ мы получим также минимальное вершинное покрытие.

Варианты

В смешанном целочисленном линейном программировании (СЦЛП) только для части переменных $x_{i}$ требуется целочисленность, в то время как остальные переменные могут быть нецелочисленными.

В булевом программировании переменные должны принимать значения 0 или 1. Заметим, что любая ограниченная целочисленная переменная может быть выражена как комбинация булевых переменных. Например, если есть целочисленная переменная $0\leq x\leq U$, её можно выразить через $\lfloor \log _{2}U\rfloor +1$ булевых переменных:

$x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$

Приложения

Есть две основные причины для использования целых переменных при моделировании задач линейного программирования:

1. Целочисленные переменные представляют величины, которые могут быть исключительно целыми. Например, невозможно построить 3.7 автомобилей.
2. Целочисленные переменные представляют решения, которые принимают значения 0 или 1.

Эти соглашения на практике встречаются часто и, таким образом, целочисленное линейное программирование может быть использовано во многих областях, некоторые из которых коротко освещены ниже.

Производственное планирование

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

Планирование

В этих задачах нужно обеспечить обслуживание и расписание работы транспортной сети. Например, задача может состоять в расстановке автобусов или поездов по маршрутам, чтобы соблюсти расписание, а также обеспечить подвижный состав водителями. Здесь булевы переменные (т.е. принимающее значение 0 или 1) определяют, назначен ли автобус или поезд на маршрут, и назначен ли водитель на конкретный автобус/поезд.

Сети передачи данных

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

Сотовые сети

Задача планирования частот в мобильных сетях GSM требует распределения допустимых частот по антеннам, чтобы обеспечить связь и минимизировать интерференцию между антеннами. Эту задачу можно сформулировать как задачу линейного программирования, в которой булевы переменные отражают, назначена ли конкретная частота конкретной антенне.

Алгоритмы

Наивный путь решения задачи ЦЛП — просто игнорировать ограничение целочисленности на переменные x, решить соответствующую задачу ЛП (которая называется линейным ослаблением ограничений задачи ЦЛП), а затем округлить компоненты решения полученной задачи. Однако полученное решение может оказаться не только не оптимальным, оно может оказаться даже недопустимым, то есть некоторые ограничения могут быть нарушены.

Использование полной унимодулярности

Хотя, в общем случае, целочисленность решения ослабленной задачи не гарантирована, если ЦЛП имеет вид $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ при условиях $A\mathbf {x} =\mathbf {b}$, где $A,\mathbf {b}$ и $\mathbf {c}$ имеют в качестве элементов целые числа и $A$ является вполне унимодулярной, тогда любое базисное допустимое решение будет целочисленным. Следовательно, решение, которое даёт симплекс-метод, будет заведомо целочисленным. Чтобы показать, что любое базисное решение такой задачи целочисленно, пусть $\mathbf {x}$ — произвольное допустимое решение. Поскольку $\mathbf {x}$ допустимо, мы знаем, что $A\mathbf {x} =\mathbf {b}$. Пусть $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ — элементы, соответствующие базисным столбцам базисного решения $\mathbf {x}$. По определению базиса существует некоторая квадратная подматрица $B$ матрицы $A$ с линейно независимыми столбцами, такая, что $B\mathbf {x} _{0}=\mathbf {b}$.

Поскольку столбцы $B$ линейно независимы и матрица $B$ квадратная, матрица $B$ неособенная, а потому при предположениях, что $B$ унимодулярна, выполняется $\det(B)=\pm 1$. Поскольку $B$ не является особенной, матрица обратима, а потому $\mathbf {x} _{0}=B^{-1}\mathbf {b}$. По определению, $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$. Здесь $B^{adj}$ означает союзную матрицу для $B$ и она целочисленна, поскольку $B$ целочисленна. Таким образом,

$\Rightarrow B^{-1}=\pm B^{adj}$ целочисленна

$\Rightarrow x_{0}=B^{-1}b$ целочисленен

$\Rightarrow$ Любое базисное допустимое решение целочисленно.

Таким образом, если матрица $A$ ЦЛП вполне унимодулярна, вместо решения задачи ЦЛП можно использовать линейное ослабление задачи, которое даст целочисленное решение.

Точные алгоритмы

Если матрица $A$ не является вполне унимодулярной, существует ряд алгоритмов, решающих задачу целочисленного линейного программирования точно. Один из классов таких алгоритмов — методы секущих плоскостей (методы Гомори), которые работают путём решения ослабленной линейной задачи с последующим добавлением линейных ограничений, которые отсекают нецелочисленное решение задачи без отсечения целочисленных допустимых решений.

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

Ленстра в 1983 показал, что в случае фиксированного числа переменных допустимое решение задачи целочисленного программирования может быть найдено за полиномиальное время.

Эвристические методы

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

Другие эвристические методы, которые могут быть применены для решения ЦЛП

• Восхождение по выпуклой поверхности
• Алгоритм имитации отжига
• Пассивная поисковая оптимизация
• Муравьиный алгоритм
• Нейронная сеть Хопфилда

Есть также некоторые другие, зависящие от задачи эвристические методы, такие как k-opt эвристика для задачи коммивояжёра. Заметим, что недостатком эвристических методов является то, что в случае неудачи поиска решения метод не определяет, произошло это вследствие отсутствия допустимого решения, или из-за неспособности алгоритма его найти. Далее обычно невозможно определить, насколько близко к оптимальному полученное этим методом решение.

Литература для дальнейшего чтения

• Карманов В. Г. Математическое программирование. — М.: Наука, 1986. — 288 с.
• Balinski M. L. Integer Programming: Methods, Uses, Computations // Management Science. — 1965. — Vol. 12, no.3. — P. 253—313. — doi:10.1287/mnsc.12.3.253.
• George L. Nemhauser, Laurence A. Wolsey. Integer and combinatorial optimization. — Wiley, 1988. — ISBN 978-0-471-82819-8.
• Alexander Schrijver. Theory of linear and integer programming. — John Wiley and Sons, 1998. — ISBN 978-0-471-98232-6.
• Laurence A. Wolsey. Integer programming. — Wiley, 1998. — ISBN 978-0-471-28366-9.
• Dimitris Bertsimas, Robert Weismantel. Optimization over integers. — Dynamic Ideas, 2005. — ISBN 978-0-9759146-2-5.
• John K. Karlof. Integer programming: theory and practice. — CRC Press, 2006. — ISBN 978-0-8493-1914-3.
• H. Paul Williams. Logic and Integer Programming. — Springer, 2009. — ISBN 978-0-387-92279-9.
• 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art / Michael Jünger, Thomas M. Liebling, Denis Naddef, George Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey. — Springer, 2009. — ISBN 978-3-540-68274-5.
• Der-San Chen, Robert G. Batson, Yu Dang. Applied Integer Programming: Modeling and Solution. — John Wiley and Sons, 2010. — ISBN 978-0-470-37306-4.

Ссылки

• A Tutorial on Integer Programming
• Conference Integer Programming and Combinatorial Optimization, IPCO
• The Aussois Combinatorial Optimization Workshop