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

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

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

21 NP-полных задач Карпа.

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

Каноническая и стандартная форма для ILPs

Целочисленная линейная программа в канонической форме выражается следующим образом:[2]

maximizecTxsubject toAxb,x0,andxZn,{\displaystyle {\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}}

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

maximizecTxsubject toAx+s=b,s0,x0,andxZn,{\displaystyle {\begin{aligned}&{\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} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}}

где

c,b{\displaystyle \mathbf {c} ,\mathbf {b} }

-векторы, а

A{\displaystyle A}

-матрица. Где все записи-целые числа. Как и в случае с линейными программами, ILP. Не находящиеся в стандартной форме. Могут быть преобразованы в стандартную форму

путем устранения неравенств. Введения слабых переменных (

s{\displaystyle \mathbf {s} }

) и замены переменных. Не ограниченных знаком. Разностью двух переменных. Ограниченных знаком

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

На графике справа показана следующая проблема.

max yx+y13x+2y122x+3y12x,y0x,yZ{\displaystyle {\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}}}

Допустимые целые точки показаны красным цветом. А красные пунктирные линии указывают на их выпуклую оболочку. Которая является наименьшим выпуклым многогранником. Содержащим все эти точки.

Синие линии вместе с координатными осями определяют многогранник релаксации LP. Который задается неравенствами без ограничения интегральности. Цель оптимизации состоит в том. Чтобы переместить черную пунктирную линию как можно выше. Все еще касаясь многогранника. Оптимальными решениями целочисленной задачи являются точки

(1,2){\displaystyle (1,2)}

,

(2,2){\displaystyle (2,2)}

оба из которых имеют объективное значение 2. Уникальным оптимумом релаксации является

(1.8,2.8){\displaystyle (1.8,2.8)}

с объективным значением 2.8. Если решение релаксации округлено до ближайших целых чисел. То для ILP это неосуществимо.

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

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

Пусть

G=(V,E){\displaystyle G=(V,E)}

это неориентированный граф. Определите линейную программу следующим образом:

minvVyvyv+yu1uvEyv0vVyvZvV{\displaystyle {\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}}}

Учитывая, что ограничения ограничиваются

yv{\displaystyle y_{v}}

либо 0, либо 1, любое допустимое решение целочисленной программы является подмножеством вершин. Первое ограничение подразумевает. Что по крайней мере одна конечная точка каждого ребра включена в это подмножество. Поэтому решение описывает вершинное покрытие. Кроме того, учитывая некоторое вершинное покрытие C,

yv{\displaystyle y_{v}}

можно установить значение 1 для любого

vC{\displaystyle v\in C}

и 0 для любого

vC{\displaystyle v\not \in C}

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

yv{\displaystyle y_{v}}

, то также найдем минимальное вершинное покрытие.]

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

xi{\displaystyle x_{i}}

ограничены целыми числами . В то время как другие переменные могут быть нецелыми.

Линейное программирование ноль-один (или двоичное целочисленное программирование) включает в себя задачи. В которых переменные ограничены либо 0, либо 1. Любая ограниченная целочисленная переменная может быть выражена как комбинация двоичных переменных.[4] Например, учитывая целочисленную переменную

0xU{\displaystyle 0\leq x\leq U}

, переменная может быть выражена с помощью

log2U+1{\displaystyle \lfloor \log _{2}U\rfloor +1}

двоичных переменных:

x=x1+2x2+4x3++2log2Uxlog2U+1.{\displaystyle 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.

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

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

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

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

Эти проблемы связаны с обслуживанием и планированием транспортных средств в транспортных сетях. Например, проблема может быть связана с назначением автобусов или метрополитенов на отдельные маршруты. Чтобы можно было соблюсти расписание. А также оснастить их водителями. Здесь бинарные переменные решения указывают. Назначается ли автобус или метро маршруту и назначается ли водитель конкретному поезду или метро. Метод программирования Он используется в частном случае целочисленного программирования. В котором все переменные решения являются целыми числами. Он может принимать значения либо как ноль. Либо как единицу.

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

Проблема территориального разделения или районирования состоит в разделении географического региона на районы для планирования некоторых операций с учетом различных критериев или ограничений. Некоторые требования к этой проблеме: смежность. Компактность. Баланс или справедливость. Уважение естественных границ и социально-экономическая однородность. Некоторые приложения для этого типа проблем включают в себя: политический район. Школьный район. Район медицинских услуг и район управления отходами.[5]

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

Цель этих задач состоит в том. Чтобы спроектировать сеть линий для установки таким образом. Чтобы был удовлетворен заранее определенный набор требований к связи и общая стоимость сети была минимальной.[6] Это требует оптимизации как топологии сети. Так и настройки пропускной способности различных линий.

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

Сотовые сети

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

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

Алгоритмы

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

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

Хотя в общем случае решение релаксации LP не будет гарантированно интегральным. Если ILP имеет такой вид

maxcTx{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }

, что

Ax=b{\displaystyle A\mathbf {x} =\mathbf {b} }

где

A{\displaystyle A}

и

b{\displaystyle \mathbf {b} }

имеют все целочисленные записи и

A{\displaystyle A}

полностью унимодулярно, то каждое базовое допустимое решение является интегральным. Следовательно, решение. Возвращаемое симплексным алгоритмом, гарантированно является интегральным. Чтобы показать. Что каждое базовое допустимое решение является интегральным. Пусть

x{\displaystyle \mathbf {x} }

это произвольное базовое допустимое решение . Поскольку

x{\displaystyle \mathbf {x} }

это осуществимо. Мы это знаем

Ax=b{\displaystyle A\mathbf {x} =\mathbf {b} }

. Пусть

x0=[xn1,xn2,,xnj]{\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}

элементы. Соответствующие базисным столбцам для базового решения

x{\displaystyle \mathbf {x} }

По определению базиса. Существует некоторая квадратная подматрица

B{\displaystyle B}

A{\displaystyle A}

с линейно независимыми столбцами такая

Bx0=b{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }

, что .

Так как столбцы

B{\displaystyle B}

линейно независимы и

B{\displaystyle B}

квадратны,

B{\displaystyle B}

то они неособы и. Следовательно. По предположению,

B{\displaystyle B}

унимодулярны и т.

det(B)=±1{\displaystyle \det(B)=\pm 1}

Д. Кроме того, поскольку

B{\displaystyle B}

оно неособо. Оно обратимо и поэтому

x0=B1b{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }

. По определению

B1=Badjdet(B)=±Badj{\displaystyle B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}}

. Здесь

Badj{\displaystyle B^{adj}}

обозначает адъюгат

B{\displaystyle B}

и является интегральным. Потому

B{\displaystyle B}

что является интегральным. Следовательно,

B1=±Badj is integral.x0=B1b is integral.Every basic feasible solution is integral.{\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}}

Таким образом. Если матрица

A{\displaystyle A}

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

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

Когда матрица

A{\displaystyle A}

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

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

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

Предположим

A{\displaystyle A}

, что это целая матрица m-by —n и целочисленный

b{\displaystyle \mathbf {b} }

вектор m-by-1. Мы фокусируемся на проблеме осуществимости. Которая заключается в том. Чтобы решить. Существует ли удовлетворительный вектор n на 1

x{\displaystyle \mathbf {x} }

Axb{\displaystyle A\mathbf {x} \leq \mathbf {b} }

.

Пусть V — максимальное абсолютное значение коэффициентов в

A{\displaystyle A}

и

b{\displaystyle \mathbf {b} }

. Если n (число переменных) является фиксированной константой. То задача выполнимости может быть решена во временном полиноме по m и log V. Это тривиально для случая n=1. Случай n=2 был решен в 1981 году Гербертом Шарфом[13]. Общий случай был решен в 1983 году Хендриком Ленстрой, объединившим идеи Ласло Ловаша и Питера ван Эмде Боаса.]

В частном случае ILP 0-1 алгоритм Ленстры эквивалентен полному перечислению: число всех возможных решений фиксировано (2n), и проверка выполнимости каждого решения может быть выполнена за время poly(m, log V). В общем случае. Когда каждая переменная может быть произвольным целым числом. Полное перечисление невозможно. Здесь алгоритм Ленстры использует идеи из Геометрии чисел. Он преобразует исходную задачу в эквивалентную со следующим свойством: либо существование решения

x{\displaystyle \mathbf {x} }

очевидно. Либо значение

xn{\displaystyle x_{n}}

(n-я переменная) принадлежит интервалу. Длина которого ограничена функцией n. В последнем случае задача сводится к ограниченному числу задач меньшей размерности.

Алгоритм Ленстры подразумевает. Что ILP разрешима за полиномиальное время также и в двойственном случае. Когда n изменяется, но m (число ограничений) постоянно.

Алгоритм Ленстры был впоследствии усовершенствован Каннаном[15], Франком и Тардосом.[16] Улучшенная среда выполнения такова

n2.5n{\displaystyle n^{2.5n}\cdot \ell }

: где

{\displaystyle \ell }

-количество входных битов,[17] которое находится в

poly(m,logV){\displaystyle {\text{poly}}(m,\log {V})}

[18]:Prop.8

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

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

Другие эвристические методы. Которые могут быть применены к ILPS, включают

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

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

Часто бывает так, что матрица

A{\displaystyle A}

, которая определяет целочисленную программу, разрежена. В частности. Это происходит. Когда матрица имеет блочную структуру. Что имеет место во многих приложениях. Разреженность матрицы можно измерить следующим образом. Граф

A{\displaystyle A}

имеет вершины . Соответствующие столбцам

A{\displaystyle A}

, и два столбца образуют ребро. Если

A{\displaystyle A}

есть строка. В которой оба столбца имеют ненулевые записи. Эквивалентно. Вершины соответствуют переменным. А две переменные образуют ребро. Если они разделяют неравенство. Мерой разреженности

d{\displaystyle d}

A{\displaystyle A}

является минимум между глубиной дерева графа

A{\displaystyle A}

и глубиной дерева графа транспонирования

A{\displaystyle A}

. Пусть

a{\displaystyle a}

числовая мера

A{\displaystyle A}

определяется как максимальное абсолютное значение любой записи

A{\displaystyle A}

. Пусть

n{\displaystyle n}

— число переменных целочисленной программы. Затем в 2018 году было показано[20], что целочисленное программирование может быть решено в сильно полиномиальном и фиксированном параметрическом управляемом времени. Параметризованном

a{\displaystyle a}

и

d{\displaystyle d}

. То есть для некоторой вычислимой функции

f{\displaystyle f}

и некоторой константы

k{\displaystyle k}

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

f(a,d)nk{\displaystyle f(a,d)n^{k}}

. В частности. Время не зависит от правой части

b{\displaystyle b}

и целевой функции

c{\displaystyle c}

. Более того, в отличие от классического результата Ленстры. Где число

n{\displaystyle n}

количество переменных-это параметр. Здесь количество

n{\displaystyle n}

переменных — это переменная часть входных данных.

  1. ^
  2. ^ Papadimitriou, C. H.; Steiglitz, K. (1998). Комбинаторная оптимизация: алгоритмы и сложность. Минеола, Нью-Йорк: Дувр. ISBN 0486402584.
  3. ^ Эриксон, Дж. (2015). (PDF). Архивировано из оригинала (PDF) 18 мая 2015 года.
  4. ^ Williams, H. P. (2009). Логика и целочисленное программирование. Международная серия исследований операций и науки управления. 130. ISBN 978-0-387-92280-5.
  5. ^ Франко, Д. Г. Б.; Штайнер, М. Т. А.; Ассеф, Ф. М. (2020). Журнал 283. doi:10.1016/j.jclepro.2020.125353.
  6. ^ Borndörfer, R.; Grötschel, M. (2012). (PDF).
  7. ^ Шарма, Дипак (2010). .
  8. ^ Франко, Д. Г. Б.; Штайнер, М. Т. А.; Ассеф, Ф. М. (2020). Журнал чистого производства. 283. doi:10.1016/j.jclepro.2020.125353.
  9. ^ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01). . Возобновляемые источники Энергии. 35 (1): 151–156. doi:10.1016/j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.
  10. ^ Ому, Акомено; Чоудхари, Ручи; Бойс, Адам (2013-10-01). . Энергетическая политика. 61: 249–266. doi:10.1016/j.enpol.2013.05.009. ISSN 0301-4215.
  11. ^ Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). 2005 IEEE Aerospace Conference: 1-13. doi:10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID 13447718.
  12. ^ Радманеш, Мохаммадреза; Кумар, Маниш (2016-03-01). . Аэрокосмическая наука и техника. 50: 149–160. doi:10.1016/j.ast.2015.12.021. ISSN 1270-9638.
  13. ^ Шарф, Герберт Э. (1981). . Эконометрика. 49 (1): 1–32. doi:10.2307/1911124. ISSN 0012-9682. JSTOR 1911124.
  14. ^ Ленстра, Х. У. (1983-11-01). . Математика исследования операций. 8 (4): 538–548. doi:10.1287/moor.8.4.538. ISSN 0364-765X.
  15. ^ Каннан, Рави (1987-08-01). . Математика исследования операций. 12 (3): 415–440. doi:10.1287/moor.12.3.415. ISSN 0364-765X.
  16. ^ Frank, András; Tardos, Éva (1987-03-01). . Комбинаторика. 7 (1): 49-65. doi:10.1007/BF02579200. ISSN 1439-6912. S2CID 45585308.
  17. ^ Bliem, Bernhard; Bredereck, Robert; Niedermeier. Rolf (2016-07-09). . Материалы Двадцать Пятой Международной совместной конференции по искусственному интеллекту. ИДЖКАЙ’16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102-108. ISBN 978-1-57735-770-4.
  18. ^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier. Rolf (2019-06-17). . Материалы конференции ACM 2019 по экономике и вычислениям. EC ’19. Феникс, Аризона, США: Ассоциация вычислительной техники: 505-523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID 195298520.
  19. ^ Гловер, Ф. (1989). . ORSA Journal on Computing. 1 (3): 4-32. doi:10.1287/ijoc.2.1.4. S2CID 207225435.
  20. ^ Кутецкий, Мартин; Левин, Асаф; Онн, Шмуэль (2018). . Михаил Вагнер: 14 страниц. arXiv:1802.05859. doi:10.4230/LIPICS.ICALP.2018.85. S2CID 3336201.

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

  • Джордж Л. Немхаузер; Лоуренс А. Уолси (1988). Целочисленная и комбинаторная оптимизация. Уайли. ISBN 978-0-471-82819-8.
  • Alexander Schrijver (1998). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. ISBN 978-0-471-98232-6.
  • Лоуренс А. Уолси (1998). Целочисленное программирование. Уайли. ISBN 978-0-471-28366-9.
  • Димитрис Берцимас; Роберт Вайсмантель (2005). Оптимизация по целымчислам . Динамические Идеи. ISBN 978-0-9759146-2-5.
  • Джон К. Карлоф (2006). Целочисленное программирование: теория и практика. CRC Press. ISBN 978-0-8493-1914-3.
  • Пол Уильямс (2009). Логика и целочисленное программирование. Спрингер. ISBN 978-0-387-92279-9.
  • Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey. Eds. (2009). 50 лет целочисленного программирования 1958-2008: От ранних лет до современных. Спрингер. ISBN 978-3-540-68274-5.
  • Дер-Сан Чен; Роберт Г. Бэтсон; Ю Данг (2010). Прикладное целочисленное программирование: Моделирование и решение. Джон Уайли и сыновья. ISBN 978-0-470-37306-4.
  • Жерар Сиерксма; Йори Цвольс (2015). Линейная и целочисленная оптимизация: Теория и практика. CRC Press. ISBN 978-1-498-71016-9.

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