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

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

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

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

Каноническая и стандартная форма для ILP [ править ]

Целочисленная линейная программа в канонической форме выражается как: ^[2]

{\ displaystyle {\ begin {align} & {\ text {maximize}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {при условии}} && A \ mathbf {x} \ leq \ mathbf {b}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ text {and}} && \ mathbf {x} \ in \ mathbb {Z} ^ {п}, \ конец {выровнено}}}

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

{\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}}

где - векторы и - матрица, где все элементы целые. Как и в случае с линейными программами, ILP в нестандартной форме можно преобразовать в стандартную форму , устранив неравенства, введя резервные переменные ( ) и заменив переменные, которые не ограничены по знаку, на разницу двух переменных с ограничением по знаку. $\mathbf {c} ,\mathbf {b}$ $A$ $\mathbf {s}$

Пример [ править ]

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

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

{\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}}

Допустимые целые точки показаны красным цветом, а красные пунктирные линии обозначают их выпуклую оболочку, которая является наименьшим выпуклым многогранником, содержащим все эти точки. Синие линии вместе с осями координат определяют многогранник релаксации ЛП, который задается неравенствами без ограничения целочисленности. Цель оптимизации - переместить черную пунктирную линию как можно дальше вверх, все еще касаясь многогранника. Оптимальные решения целочисленной задачи являются точками и которые оба имеют объективное значение 2. Уникальный оптимум релаксации с объективным значением 2,8. Если решение ослабления округляется до ближайших целых чисел, это невозможно для ILP. $(1,2)$ $(2,2)$ $(1.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}}

Учитывая, что ограничения ограничиваются 0 или 1, любое возможное решение целочисленной программы является подмножеством вершин. Первое ограничение подразумевает, что в это подмножество включена по крайней мере одна конечная точка каждого ребра. Следовательно, решение описывает вершинное покрытие. Кроме того, для некоторого покрытия вершин C можно установить значение 1 для любого и 0 для любого, что дает нам возможное решение целочисленной программы. Таким образом, мы можем заключить, что если мы минимизируем сумму, мы также нашли минимальное вершинное покрытие. ^[3] $y_{v}$ $y_{v}$ $v\in C$ $v\not \in C$ $y_{v}$

Варианты [ править ]

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

Линейное программирование нуля или единицы (или двоичное целочисленное программирование ) связано с проблемами, в которых переменные ограничены равными 0 или 1. Любая ограниченная целочисленная переменная может быть выражена как комбинация двоичных переменных. ^[4] Например, для целочисленной переменной, переменная может быть выражена с помощью двоичных переменных: $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}.

Приложения [ править ]

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

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

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

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

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

Планирование [ править ]

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

Территориальное разделение [ править ]

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

Телекоммуникационные сети [ править ]

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

Сотовые сети [ править ]

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

Другие приложения [ править ]

Управление твердыми бытовыми отходами ^[8]
Согласование денежных потоков
Оптимизация энергосистемы ^[9]^[10]
Л руководство ^[11]^[12]

Алгоритмы [ править ]

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

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

В то время как в целом решение LP релаксации не будет гарантированно составлять единое целое, если ИЛП имеет вид такой , что , где и есть все целые записи и является полностью унимодулярная , то каждый основной возможным решением является неотъемлемой частью. Следовательно, решение, возвращаемое симплексным алгоритмом , гарантированно будет целым. Чтобы показать, что каждое основное допустимое решение является целым, позвольте быть произвольным основным допустимым решением. Поскольку это возможно, мы это знаем . Позвольте быть элементы, соответствующие столбцам базиса для основного решения . По определению базиса, есть некоторые квадратные подматрицы из $\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^{adj}}{\det(B)}}=\pm B^{adj}$ $B^{adj}$ $B$ $B$

{\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}}

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

Точные алгоритмы [ править ]

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

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

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

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

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

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

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

Впоследствии алгоритм Ленстры был улучшен Каннаном ^[15] и Фрэнком и Тардосом. ^[16] Усовершенствованная среда выполнения:, где - количество входных битов, ^[17] в . ^[18]^:^{Предложение 8} $n^{2.5n}\cdot \ell$ $\ell$ ${\text{poly}}(m,\log {V})$

Эвристические методы [ править ]

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

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

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

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

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

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

См. Также [ править ]

Метод наименьших квадратов с ограничениями

Ссылки [ править ]

^ «Смешанное целочисленное линейное программирование (MILP): формулировка модели» (PDF) . Проверено 16 апреля 2018 года .
^ Пападимитриу, Швейцария ; Стейглиц, К. (1998). Комбинаторная оптимизация: алгоритмы и сложность . Минеола, Нью-Йорк: Дувр. ISBN 0486402584.
^ Эриксон, Дж. (2015). «Сокращение целочисленного программирования» (PDF) . Архивировано 18 мая 2015 года из оригинального (PDF) .
^ Уильямс, HP (2009). Логическое и целочисленное программирование . Международная серия исследований по операциям и менеджменту. 130 . ISBN 978-0-387-92280-5.
^ Франко, DGB; Штайнер, MTA; Ассеф, FM (2020). «Оптимизация разделения полигонов для захоронения отходов в штате Парана, Бразилия». Журнал чистого производства . 283 . DOI : 10.1016 / j.jclepro.2020.125353 .
^ Borndörfer, R .; Грёчель, М. (2012). «Проектирование телекоммуникационных сетей методом целочисленного программирования» (PDF) .
^ Шарма, Дипак (2010). «Частотное планирование» .
^ Франко, DGB; Штайнер, MTA; Ассеф, FM (2020). «Оптимизация разделения полигонов для захоронения отходов в штате Парана, Бразилия». Журнал чистого производства . 283 . DOI : 10.1016 / j.jclepro.2020.125353 .
^ Мораис, Хьюго; Кадар, Петер; Фариа, Педро; Vale, Zita A .; Ходр, HM (01.01.2010). «Оптимальное планирование возобновляемой микросети в изолированной зоне нагрузки с использованием смешанно-целочисленного линейного программирования» . Возобновляемая энергия . 35 (1): 151–156. DOI : 10.1016 / j.renene.2009.02.031 . ЛВП : 10400,22 / 1585 . ISSN 0960-1481 .
^ Ому, Акомено; Чоудхари, Ручи; Бойс, Адам (01.10.2013). «Оптимизация системы распределенных энергоресурсов с использованием смешанного целочисленного линейного программирования» . Энергетическая политика . 61 : 249–266. DOI : 10.1016 / j.enpol.2013.05.009 . ISSN 0301-4215 .
^ Schouwenaars, T .; Валенти, М .; Feron, E .; Как, Дж. (2005). «Результаты внедрения и летных испытаний системы управления БПЛА на основе MILP». 2005 IEEE Aerospace Conference : 1–13. DOI : 10.1109 / AERO.2005.1559600 . ISBN 0-7803-8870-4. S2CID 13447718 .
^ Радманеш, Мохаммадреза; Кумар, Маниш (01.03.2016). «Формирование полета БЛА при наличии движущихся препятствий с использованием быстродинамического смешанного целочисленного линейного программирования» . Аэрокосмическая наука и технологии . 50 : 149–160. DOI : 10.1016 / j.ast.2015.12.021 . ISSN 1270-9638 .
Перейти ↑ Scarf, Herbert E. (1981). «Производственные наборы с неделимостью, часть I: общие положения» . Econometrica . 49 (1): 1–32. DOI : 10.2307 / 1911124 . ISSN 0012-9682 . JSTOR 1911124 .
^ Ленстра, HW (1983-11-01). «Целочисленное программирование с фиксированным числом переменных» . Математика исследования операций . 8 (4): 538–548. DOI : 10.1287 / moor.8.4.538 . ISSN 0364-765X .
^ Kannan, Рави (1987-08-01). "Теорема Минковского о выпуклом теле и целочисленное программирование" . Математика исследования операций . 12 (3): 415–440. DOI : 10.1287 / moor.12.3.415 . ISSN 0364-765X .
^ Франк, Андраш; Тардос, Ива (1987-03-01). «Применение одновременного диофантова приближения в комбинаторной оптимизации» . Combinatorica . 7 (1): 49–65. DOI : 10.1007 / BF02579200 . ISSN 1439-6912 . S2CID 45585308 .
^ Блием, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (09.07.2016). «Сложность эффективного распределения ресурсов без зависти: мало агентов, ресурсов или уровней полезности» . Материалы Двадцать пятой международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
^ Бредерек, Роберт; Качмарчик, Анджей; Кноп, Душан; Нидермайер, Рольф (17.06.2019). "Справедливое распределение высокой кратности: Lenstra наделена N-кратным целочисленным программированием" . Материалы конференции ACM по экономике и вычислениям 2019 . EC '19. Феникс, Аризона, США: Ассоциация вычислительной техники: 505–523. DOI : 10.1145 / 3328526.3329649 . ISBN 978-1-4503-6792-9. S2CID 195298520 .
^ Гловер, Ф. (1989). «Табу-поиск-Часть II» . ORSA Journal on Computing . 1 (3): 4–32. DOI : 10,1287 / ijoc.2.1.4 . S2CID 207225435 .
^ Koutecký, Мартин; Левин, Асаф; Онн, Шмуэль (2018). "Параметризованный сильно полиномиальный алгоритм для блочно-структурированных целочисленных программ" . Михаэль Вагнер: 14 страниц. arXiv : 1802.05859 . DOI : 10,4230 / LIPICS.ICALP.2018.85 . S2CID 3336201 . Cite journal requires |journal= (help)

Дальнейшее чтение [ править ]

Джордж Л. Немхаузер ; Лоуренс А. Вулси (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). Целочисленное программирование: теория и практика . CRC Press. ISBN 978-0-8493-1914-3.
Х. Пол Уильямс (2009). Логическое и целочисленное программирование . Springer. ISBN 978-0-387-92279-9.
Михаэль Юнгер; Томас М. Либлинг; Денис Наддеф; Джордж Немхаузер ; Уильям Р. Пуллибланк ; Герхард Райнельт; Джованни Ринальди; Лоуренс А. Вулси, ред. (2009). 50 лет целочисленного программирования 1958–2008: от первых лет до современного состояния . Springer. ISBN 978-3-540-68274-5.
Дер-Сан Чен; Роберт Дж. Батсон; Ю Данг (2010). Прикладное целочисленное программирование: моделирование и решение . Джон Уайли и сыновья. ISBN 978-0-470-37306-4.
Жерар Сирксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . CRC Press. ISBN 978-1-498-71016-9.

Внешние ссылки [ править ]

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

[1] «Смешанное целочисленное линейное программирование (MILP): формулировка модели» (PDF) . Проверено 16 апреля 2018 года .

[optBook-2] Пападимитриу, Швейцария ; Стейглиц, К. (1998). Комбинаторная оптимизация: алгоритмы и сложность . Минеола, Нью-Йорк: Дувр. ISBN 0486402584.

[3] Эриксон, Дж. (2015). «Сокращение целочисленного программирования» (PDF) . Архивировано 18 мая 2015 года из оригинального (PDF) .

[4] Уильямс, HP (2009). Логическое и целочисленное программирование . Международная серия исследований по операциям и менеджменту. 130 . ISBN 978-0-387-92280-5.

[5] Франко, DGB; Штайнер, MTA; Ассеф, FM (2020). «Оптимизация разделения полигонов для захоронения отходов в штате Парана, Бразилия». Журнал чистого производства . 283 . DOI : 10.1016 / j.jclepro.2020.125353 .

[6] Borndörfer, R .; Грёчель, М. (2012). «Проектирование телекоммуникационных сетей методом целочисленного программирования» (PDF) .

[7] Шарма, Дипак (2010). «Частотное планирование» .

[8] Франко, DGB; Штайнер, MTA; Ассеф, FM (2020). «Оптимизация разделения полигонов для захоронения отходов в штате Парана, Бразилия». Журнал чистого производства . 283 . DOI : 10.1016 / j.jclepro.2020.125353 .

[9] Мораис, Хьюго; Кадар, Петер; Фариа, Педро; Vale, Zita A .; Ходр, HM (01.01.2010). «Оптимальное планирование возобновляемой микросети в изолированной зоне нагрузки с использованием смешанно-целочисленного линейного программирования» . Возобновляемая энергия . 35 (1): 151–156. DOI : 10.1016 / j.renene.2009.02.031 . ЛВП : 10400,22 / 1585 . ISSN 0960-1481 .

[10] Ому, Акомено; Чоудхари, Ручи; Бойс, Адам (01.10.2013). «Оптимизация системы распределенных энергоресурсов с использованием смешанного целочисленного линейного программирования» . Энергетическая политика . 61 : 249–266. DOI : 10.1016 / j.enpol.2013.05.009 . ISSN 0301-4215 .

[11] Schouwenaars, T .; Валенти, М .; Feron, E .; Как, Дж. (2005). «Результаты внедрения и летных испытаний системы управления БПЛА на основе MILP». 2005 IEEE Aerospace Conference : 1–13. DOI : 10.1109 / AERO.2005.1559600 . ISBN 0-7803-8870-4. S2CID 13447718 .

[12] Радманеш, Мохаммадреза; Кумар, Маниш (01.03.2016). «Формирование полета БЛА при наличии движущихся препятствий с использованием быстродинамического смешанного целочисленного линейного программирования» . Аэрокосмическая наука и технологии . 50 : 149–160. DOI : 10.1016 / j.ast.2015.12.021 . ISSN 1270-9638 .

[13] Перейти ↑ Scarf, Herbert E. (1981). «Производственные наборы с неделимостью, часть I: общие положения» . Econometrica . 49 (1): 1–32. DOI : 10.2307 / 1911124 . ISSN 0012-9682 . JSTOR 1911124 .

[14] Ленстра, HW (1983-11-01). «Целочисленное программирование с фиксированным числом переменных» . Математика исследования операций . 8 (4): 538–548. DOI : 10.1287 / moor.8.4.538 . ISSN 0364-765X .

[15] Kannan, Рави (1987-08-01). "Теорема Минковского о выпуклом теле и целочисленное программирование" . Математика исследования операций . 12 (3): 415–440. DOI : 10.1287 / moor.12.3.415 . ISSN 0364-765X .

[16] Франк, Андраш; Тардос, Ива (1987-03-01). «Применение одновременного диофантова приближения в комбинаторной оптимизации» . Combinatorica . 7 (1): 49–65. DOI : 10.1007 / BF02579200 . ISSN 1439-6912 . S2CID 45585308 .

[17] Блием, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (09.07.2016). «Сложность эффективного распределения ресурсов без зависти: мало агентов, ресурсов или уровней полезности» . Материалы Двадцать пятой международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4.

[18] Бредерек, Роберт; Качмарчик, Анджей; Кноп, Душан; Нидермайер, Рольф (17.06.2019). "Справедливое распределение высокой кратности: Lenstra наделена N-кратным целочисленным программированием" . Материалы конференции ACM по экономике и вычислениям 2019 . EC '19. Феникс, Аризона, США: Ассоциация вычислительной техники: 505–523. DOI : 10.1145 / 3328526.3329649 . ISBN 978-1-4503-6792-9. S2CID 195298520 .

[19] Гловер, Ф. (1989). «Табу-поиск-Часть II» . ORSA Journal on Computing . 1 (3): 4–32. DOI : 10,1287 / ijoc.2.1.4 . S2CID 207225435 .

[20] Koutecký, Мартин; Левин, Асаф; Онн, Шмуэль (2018). "Параметризованный сильно полиномиальный алгоритм для блочно-структурированных целочисленных программ" . Михаэль Вагнер: 14 страниц. arXiv : 1802.05859 . DOI : 10,4230 / LIPICS.ICALP.2018.85 . S2CID 3336201 . Cite journal requires |journal= (help)

[1]