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

Задача целочисленного программирования — это программа математической оптимизации или осуществимости , в которой некоторые или все переменные ограничены целыми числами . Во многих случаях этот термин относится к целочисленному линейному программированию (ILP), в котором целевая функция и ограничения (кроме целочисленных ограничений) являются линейными .

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

Если некоторые переменные решения не являются дискретными, проблема известна как задача смешанно-целочисленного программирования .

ILP

В целочисленном линейном программировании каноническая форма отличается от стандартной формы . Целочисленная линейная программа в канонической форме выражается так (заметим, что это $\mathbf {x}$ вектор, который предстоит определить):

${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

а ILP в стандартной форме выражается как

${\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}$

где $\mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}$ являются векторами и $A\in \mathbb {R} ^{m\times n}$является матрицей. Как и в случае с линейными программами, ILP, не имеющие стандартной формы, могут быть преобразованы в стандартную форму путем исключения неравенств и введения слабых переменных ( $\mathbf {s}$) и заменяя переменные, которые не имеют ограничений по знаку, разницей двух переменных с ограничениями по знаку.

Пример

IP-многогранник с LP-релаксацией

График справа показывает следующую проблему.

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

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

Доказательство

Ниже приводится сведение от минимального вершинного покрытия к целочисленному программированию, которое послужит доказательством 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}&\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}$ мы также нашли минимальное вершинное покрытие.

Варианты

Смешанно-целочисленное линейное программирование ( MILP ) включает в себя задачи, в которых только некоторые переменные $x_{i}$, должны быть целыми числами, в то время как другие переменные могут быть нецелыми.

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

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

Приложения

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

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

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

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

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

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

Эти проблемы связаны с планированием обслуживания и транспортных средств в транспортных сетях. Например, проблема может заключаться в распределении автобусов или метро по отдельным маршрутам для соблюдения расписания, а также в оснащении их водителями. Здесь двоичные переменные решения указывают, назначен ли автобус или метро маршруту и ​​назначен ли водитель конкретному поезду или метро. Техника программирования ноль-единица была успешно применена для решения проблемы выбора проекта, в которой проекты являются взаимоисключающими и/или технологически взаимозависимыми. Он используется в частном случае целочисленного программирования, в котором все переменные решения являются целыми числами. Переменная может принимать только значения ноль или единица.

Территориальное разделение

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

Телекоммуникационные сети

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

Сотовые сети

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

Другие приложения

• Сопоставление денежных потоков
• энергетической системы Оптимизация
• БПЛА наведение
• транзитной карты Схема

Алгоритмы

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

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

Хотя в целом решение проблемы релаксации ЛП не будет гарантированно целочисленным, если ILP имеет вид $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ такой, что $A\mathbf {x} =\mathbf {b}$ где $A$ и $\mathbf {b}$ иметь все целочисленные записи и $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^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$. Здесь $B^{\mathrm {adj} }$ обозначает сопряжение ​ $B$ и является целым, поскольку $B$является интегральным. Поэтому,

$${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$$

Таким образом, если матрица $A$ ILP полностью унимодулярна, вместо использования алгоритма ILP для решения релаксации LP можно использовать симплексный метод, и решение будет целочисленным.

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

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

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

Точные алгоритмы для небольшого числа переменных

Предполагать $A$ является целочисленной матрицей размером m на n и $\mathbf {b}$является целочисленным вектором m -x1. Мы сосредотачиваемся на проблеме осуществимости, которая заключается в том, чтобы решить, существует ли вектор n -x1. $\mathbf {x}$ удовлетворяющий $A\mathbf {x} \leq \mathbf {b}$.

Пусть V — максимальное абсолютное значение коэффициентов в $A$ и $\mathbf {b}$. Если n (количество переменных) является фиксированной константой, то проблема осуществимости может быть решена за полиномиальное от m и log V время . Это тривиально для случая n =1. Случай n =2 был решен в 1981 году Гербертом Скарфом . Общий случай был решен в 1983 году Хендриком Ленстра , объединив идеи Ласло Ловаса и Питера ван Эмде Боаса . Теорема Дуаньона утверждает, что целочисленная программа осуществима, если каждое подмножество $2^{n}$ограничения возможны; метод, сочетающий этот результат с алгоритмами для задач типа ЛП, может быть использован для решения целочисленных программ за время, линейное по величине. $m$ и управляемый с фиксированными параметрами (FPT) в $n$, но, возможно, дважды экспоненциальный по $n$, без зависимости от $V$.

В частном случае ILP 0–1 алгоритм Ленстры эквивалентен полному перебору: число всех возможных решений фиксировано (2 ^н ), а проверка осуществимости каждого решения может быть выполнена за время poly( m , log V ). В общем случае, когда каждая переменная может быть произвольным целым числом, полное перечисление невозможно. Здесь алгоритм Ленстры использует идеи из «Геометрии чисел» . Он преобразует исходную задачу в эквивалентную, обладающую следующим свойством: либо существование решения $\mathbf {x}$ очевидно, или значение $x_{n}$( n -я переменная) принадлежит интервалу, длина которого ограничена функцией от n . В последнем случае задача сводится к ограниченному числу задач меньшей размерности. Сложность алгоритма во время выполнения была улучшена в несколько этапов:

• Оригинальный алгоритм Lenstra имел время выполнения $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$.
• Каннан представил улучшенный алгоритм со временем выполнения $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$.
• Фрэнк и Тардос представил улучшенный алгоритм со временем выполнения $n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}$.

• Дадуш представил улучшенный алгоритм со временем выполнения $n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}$.

• Рейс и Ротвосс представил улучшенный алгоритм со временем выполнения $(\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}$.

Эти алгоритмы также подходят для смешанных целочисленных линейных программ (MILP) — программ, в которых некоторые переменные являются целочисленными, а некоторые — вещественными. Оригинальный алгоритм Lenstra имеет время выполнения $2^{O(n^{3})}\cdot poly(d,L)$, где n — количество целочисленных переменных, d — количество непрерывных переменных, а L — размер двоичного кодирования задачи. Используя методы из более поздних алгоритмов, фактор $2^{O(n^{3})}$ можно улучшить до $2^{O(n\log n)}$ или чтобы $n^{n}$.

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

Поскольку целочисленное линейное программирование является NP-сложным , многие экземпляры проблем неразрешимы, и поэтому вместо них необходимо использовать эвристические методы. Например, табу-поиск можно использовать для поиска решений ПДОДИ. Чтобы использовать поиск с табу для решения задач ILP, ходы можно определить как увеличение или уменьшение переменной с целочисленным ограничением допустимого решения, сохраняя при этом все остальные переменные с целочисленными ограничениями постоянными. Затем вычисляются неограниченные переменные. Кратковременная память может состоять из ранее опробованных решений, тогда как среднесрочная память может состоять из значений целочисленных переменных, которые привели к высоким целевым значениям (при условии, что ILP является проблемой максимизации). Наконец, долговременная память может направлять поиск целочисленных значений, которые ранее не использовались.

Другие эвристические методы, которые можно применить к ILP, включают:

• скалолазание
• Имитация отжига
• Реактивная поисковая оптимизация
• Оптимизация колонии муравьев
• Нейронные сети Хопфилда

Существует также множество других эвристик, специфичных для конкретной задачи, например эвристика k-opt для задачи коммивояжера. Недостатком эвристических методов является то, что если они не могут найти решение, невозможно определить, происходит ли это из-за отсутствия допустимого решения или алгоритм просто не смог его найти. Кроме того, обычно невозможно количественно определить, насколько близко к оптимальному решение, возвращаемое этими методами.

Разреженное целочисленное программирование

Часто бывает, что матрица $A$который определяет, что целочисленная программа является разреженной . В частности, это происходит, когда матрица имеет блочную структуру , что имеет место во многих приложениях. Разреженность матрицы можно измерить следующим образом. График ​ ​ $A$ имеет вершины, соответствующие столбцам $A$, и два столбца образуют ребро, если $A$имеет строку, в которой оба столбца имеют ненулевые записи. Эквивалентно, вершины соответствуют переменным, а две переменные образуют ребро, если они разделяют неравенство. разреженности Мера $d$ из $A$ – это минимум глубины дерева графа $A$ и глубину дерева графа транспонирования $A$. Позволять $a$ быть числовой мерой $A$ определяется как максимальное абсолютное значение любой записи $A$. Позволять $n$— количество переменных целочисленной программы. Потом его показали в 2018 году что целочисленное программирование может быть решено за строго полиномиальное и управляемое время с фиксированными параметрами, параметризованное $a$ и $d$. То есть для некоторой вычислимой функции $f$ и некоторая константа $k$, целочисленное программирование можно решить за время $f(a,d)n^{k}$. В частности, время не зависит от правой части $b$ и целевая функция $c$. Более того, в отличие от классического результата Ленстры, где число $n$ переменных является параметром, здесь число $n$ переменных — это переменная часть ввода.

См. также

• Ограниченные наименьшие квадраты
• Диофантово уравнение - Полиномиальное уравнение, целочисленные решения которого ищутся.

Дальнейшее чтение

• Джордж Л. Немхаузер ; Лоуренс А. Уолси (1988). Целочисленная и комбинаторная оптимизация . Уайли. ISBN  978-0-471-82819-8 .
• Александр Шрийвер (1998). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. ISBN  978-0-471-98232-6 .
• Лоуренс А. Уолси (1998). Целочисленное программирование . Уайли. ISBN  978-0-471-28366-9 .
• Димитрис Берцимас; Роберт Вейсмантель (2005). Оптимизация по целым числам . Динамические идеи. ISBN  978-0-9759146-2-5 .
• Джон К. Карлоф (2006). Целочисленное программирование: теория и практика . ЦРК Пресс. ISBN  978-0-8493-1914-3 .
• Х. Пол Уильямс (2009). Логическое и целочисленное программирование . Спрингер. ISBN  978-0-387-92279-9 .
• Михаэль Юнгер; Томас М. Либлинг; Денис Наддеф; Джордж Немхаузер ; Уильям Р. Пуллибланк ; Герхард Рейнельт; Джованни Ринальди; Лоуренс А. Уолси, ред. (2009). 50 лет целочисленного программирования, 1958–2008: от ранних лет до современных достижений . Спрингер. ISBN  978-3-540-68274-5 .
• Дер-Сан Чен; Роберт Г. Бэтсон; Ю Данг (2010). Прикладное целочисленное программирование: моделирование и решение . Джон Уайли и сыновья. ISBN  978-0-470-37306-4 .
• Жерар Сиерксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . ЦРК Пресс. ISBN  978-1-498-71016-9 .

Внешние ссылки

• Учебник по целочисленному программированию
• Конференция «Целочисленное программирование и комбинаторная оптимизация», IPCO
• Семинар по комбинаторной оптимизации Aussois