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

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

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

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

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

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

{\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}$ ) и заменяя переменные, не имеющие ограничений по знаку, разницей двух переменных с ограничениями по знаку.

Пример

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

{\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-твердости

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

Варианты

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

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

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

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

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

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

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

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

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

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

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

Сотовые сети

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

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

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

Алгоритмы

Наивный способ решения 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 году Гербертом Скарфом . ^[13] Общий случай был решен в 1983 году Хендриком Ленстра , объединив идеи Ласло Ловаса и Питера ван Эмде Боаса . ^[14] Теорема Дуаньона утверждает, что целочисленная программа осуществима, если каждое подмножество $2^{n}$ ограничения возможны; метод, сочетающий этот результат с алгоритмами для задач типа ЛП, может быть использован для решения целочисленных программ за время, линейное по величине. $m$ и управляемый с фиксированными параметрами (FPT) в $n$ , но, возможно, дважды экспоненциальный по $n$ , без зависимости от $V$ . ^[15]

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

Оригинальный алгоритм Lenstra ^[14] имел время выполнения $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ .
Каннан ^[16] представил улучшенный алгоритм со временем выполнения $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ . ^[17]
Фрэнк и Тардос ^[18] представил улучшенный алгоритм со временем выполнения $n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ . ^[19]^[20]^{: Положение 8}

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Карп, Ричард М. (1972). «Сводимость комбинаторных задач» (PDF) . В Р.Э. Миллере; Дж. У. Тэтчер; Дж. Д. Болингер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. стр. 85–103. дои : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6 .
^ «Смешанно-целочисленное линейное программирование (MILP): формулировка модели» (PDF) . Проверено 16 апреля 2018 г.
^ Пападимитриу, Швейцария ; Стейглиц, К. (1998). Комбинаторная оптимизация: алгоритмы и сложность . Минеола, Нью-Йорк: Дувр. ISBN 0486402584 .
^ Эриксон, Дж. (2015). «Сокращение целочисленного программирования» (PDF) . Архивировано из оригинала (PDF) 18 мая 2015 года.
^ Уильямс, HP (2009). Логическое и целочисленное программирование . Международная серия по исследованию операций и науке управления. Том. 130. ИСБН 978-0-387-92280-5 .
^ Борндорфер, Р.; Гретшель, М. (2012). «Проектирование телекоммуникационных сетей методом целочисленного программирования» (PDF) .
^ Шарма, Дипак (2010). «Частотное планирование» .
^ Мораис, Хьюго; Кадар, Питер; Фариа, Педро; Вейл, Зита А.; Ходр, Ее Величество (1 января 2010 г.). «Оптимальное планирование возобновляемой микросети в изолированной зоне нагрузки с использованием смешанно-целочисленного линейного программирования» . Возобновляемая энергия . 35 (1): 151–156. doi : 10.1016/j.renene.2009.02.031 . hdl : 10400.22/1585 . ISSN 0960-1481 .
^ Ому, Акомено; Чоудхари, Ручи; Бойс, Адам (01 октября 2013 г.). «Оптимизация системы распределенных энергоресурсов с использованием смешанного целочисленного линейного программирования» . Энергетическая политика . 61 : 249–266. дои : 10.1016/j.enpol.2013.05.009 . ISSN 0301-4215 . S2CID 29369795 .
^ Шувенаарс, Т.; Валенти, М.; Ферон, Э.; Как, Дж. (2005). «Результаты внедрения и летных испытаний системы наведения БПЛА на базе MILP». Аэрокосмическая конференция IEEE 2005 г. стр. 1–13. дои : 10.1109/AERO.2005.1559600 . ISBN 0-7803-8870-4 . S2CID 13447718 .
^ Радманеш, Мохаммадреза; Кумар, Маниш (01 марта 2016 г.). «Формирование полета БПЛА при наличии движущихся препятствий с использованием быстродинамического смешанного целочисленного линейного программирования» . Аэрокосмическая наука и технология . 50 : 149–160. дои : 10.1016/j.ast.2015.12.021 . ISSN 1270-9638 .
^ Баст, Ханна; Брози, Патрик; Сторандт, Сабина (05 октября 2017 г.). «Эффективное создание географически точных транзитных карт». arXiv : 1710.02226 [ cs.CG ].
^ Шарф, Герберт Э. (1981). «Производственные множества с неделимостью, Часть I: Общие положения» . Эконометрика . 49 (1): 1–32. дои : 10.2307/1911124 . ISSN 0012-9682 . JSTOR 1911124 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Ленстра, HW (1 ноября 1983 г.). «Целочисленное программирование с фиксированным числом переменных» . Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . дои : 10.1287/moor.8.4.538 . ISSN 0364-765X .
^ Амента, Нина ; Де Лоэра, Хесус А .; Соберон, Пабло (2017). «Теорема Хелли: новые вариации и приложения». В Харрингтоне, Хизер А .; Омар, Мохамед; Райт, Мэтью (ред.). Материалы специальной сессии AMS по алгебраическим и геометрическим методам в прикладной дискретной математике, состоявшейся в Сан-Антонио, штат Техас, 11 января 2015 г. Современная математика. Том. 685. Провиденс, Род-Айленд: Американское математическое общество. стр. 55–95. arXiv : 1508.07606 . дои : 10.1090/conm/685 . ISBN 9781470423216 . МР 3625571 .
^ Каннан, Рави (1 августа 1987 г.). «Теорема Минковского о выпуклом теле и целочисленное программирование» . Математика исследования операций . 12 (3): 415–440. дои : 10.1287/moor.12.3.415 . ISSN 0364-765X . S2CID 495512 .
^ Гоеманс, Мишель X .; Ротвосс, Томас (07.11.2020). «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» . Журнал АКМ . 67 (6): 38:1–38:21. дои : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN 0004-5411 . S2CID 227154747 .
^ Франк, Андраш; Тардос, Ева (1 марта 1987 г.). «Применение одновременной диофантовой аппроксимации в комбинаторной оптимизации» . Комбинаторика . 7 (1): 49–65. дои : 10.1007/BF02579200 . ISSN 1439-6912 . S2CID 45585308 .
^ Блим, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (9 июля 2016 г.). «Сложность эффективного и свободного от зависти распределения ресурсов: мало агентов, ресурсов или уровней полезности» . Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4 .
^ Бредерек, Роберт; Качмарчик, Анджей; Кноп, Душан; Нидермайер, Рольф (17 июня 2019 г.). «Справедливое распределение с высокой кратностью: Lenstra на базе N-кратного целочисленного программирования» . Материалы конференции ACM по экономике и вычислениям 2019 года . ЕС '19. Финикс, Аризона, США: Ассоциация вычислительной техники. стр. 505–523. дои : 10.1145/3328526.3329649 . ISBN 978-1-4503-6792-9 . S2CID 195298520 .
^ Дадуш, Дэниел (14 июня 2012 г.). «Целочисленное программирование, решетчатые алгоритмы и детерминированная оценка объема .
^ Рейс, Виктор; Ротвосс, Томас (26 марта 2023 г.). «Гипотеза о плоскостности подпространства и более быстрое целочисленное программирование» .
↑ Перейти обратно: Перейти обратно: ^а ^б Хильдебранд, Роберт (07 октября 2016 г.). «Алгоритм FPT для программы смешанных целых чисел» . Обмен стеками теоретической информатики . Проверено 21 мая 2024 г.
^ Гловер, Ф. (1989). «Поиск Табу-Часть II». Журнал ORSA по вычислительной технике . 1 (3): 4–32. дои : 10.1287/ijoc.2.1.4 . S2CID 207225435 .
^ Кутецкий, Мартин; Левин, Асаф; Онн, Шмуэль (2018). «Параметризованный сильно полиномиальный алгоритм для целочисленных программ с блочной структурой». В Хацигианнакисе, Иоаннис; Какламанис, Христос; Маркс, Даниэль; Саннелла, Дональд (ред.). 45-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2018, 9–13 июля 2018 г., Прага, Чехия . ЛИПИ. Том. 107. Замок Дагштуль – Центр информатики Лейбница. стр. 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .

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

Джордж Л. Немхаузер ; Лоуренс А. Уолси (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 .

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

[1] Карп, Ричард М. (1972). «Сводимость комбинаторных задач» (PDF) . В Р.Э. Миллере; Дж. У. Тэтчер; Дж. Д. Болингер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. стр. 85–103. дои : 10.1007/978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6 .

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

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

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

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

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

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

[8] Мораис, Хьюго; Кадар, Питер; Фариа, Педро; Вейл, Зита А.; Ходр, Ее Величество (1 января 2010 г.). «Оптимальное планирование возобновляемой микросети в изолированной зоне нагрузки с использованием смешанно-целочисленного линейного программирования» . Возобновляемая энергия . 35 (1): 151–156. doi : 10.1016/j.renene.2009.02.031 . hdl : 10400.22/1585 . ISSN 0960-1481 .

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

[10] Шувенаарс, Т.; Валенти, М.; Ферон, Э.; Как, Дж. (2005). «Результаты внедрения и летных испытаний системы наведения БПЛА на базе MILP». Аэрокосмическая конференция IEEE 2005 г. стр. 1–13. дои : 10.1109/AERO.2005.1559600 . ISBN 0-7803-8870-4 . S2CID 13447718 .

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

[12] Баст, Ханна; Брози, Патрик; Сторандт, Сабина (05 октября 2017 г.). «Эффективное создание географически точных транзитных карт». arXiv : 1710.02226 [ cs.CG ].

[13] Шарф, Герберт Э. (1981). «Производственные множества с неделимостью, Часть I: Общие положения» . Эконометрика . 49 (1): 1–32. дои : 10.2307/1911124 . ISSN 0012-9682 . JSTOR 1911124 .

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

[15] Амента, Нина ; Де Лоэра, Хесус А .; Соберон, Пабло (2017). «Теорема Хелли: новые вариации и приложения». В Харрингтоне, Хизер А .; Омар, Мохамед; Райт, Мэтью (ред.). Материалы специальной сессии AMS по алгебраическим и геометрическим методам в прикладной дискретной математике, состоявшейся в Сан-Антонио, штат Техас, 11 января 2015 г. Современная математика. Том. 685. Провиденс, Род-Айленд: Американское математическое общество. стр. 55–95. arXiv : 1508.07606 . дои : 10.1090/conm/685 . ISBN 9781470423216 . МР 3625571 .

[16] Каннан, Рави (1 августа 1987 г.). «Теорема Минковского о выпуклом теле и целочисленное программирование» . Математика исследования операций . 12 (3): 415–440. дои : 10.1287/moor.12.3.415 . ISSN 0364-765X . S2CID 495512 .

[17] Гоеманс, Мишель X .; Ротвосс, Томас (07.11.2020). «Полиномиальность упаковки контейнеров с постоянным количеством типов предметов» . Журнал АКМ . 67 (6): 38:1–38:21. дои : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN 0004-5411 . S2CID 227154747 .

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

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

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

[21] Дадуш, Дэниел (14 июня 2012 г.). «Целочисленное программирование, решетчатые алгоритмы и детерминированная оценка объема .

[22] Рейс, Виктор; Ротвосс, Томас (26 марта 2023 г.). «Гипотеза о плоскостности подпространства и более быстрое целочисленное программирование» .

[:1-23] Перейти обратно: Перейти обратно: ^а ^б Хильдебранд, Роберт (07 октября 2016 г.). «Алгоритм FPT для программы смешанных целых чисел» . Обмен стеками теоретической информатики . Проверено 21 мая 2024 г.

[24] Гловер, Ф. (1989). «Поиск Табу-Часть II». Журнал ORSA по вычислительной технике . 1 (3): 4–32. дои : 10.1287/ijoc.2.1.4 . S2CID 207225435 .

[25] Кутецкий, Мартин; Левин, Асаф; Онн, Шмуэль (2018). «Параметризованный сильно полиномиальный алгоритм для целочисленных программ с блочной структурой». В Хацигианнакисе, Иоаннис; Какламанис, Христос; Маркс, Даниэль; Саннелла, Дональд (ред.). 45-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2018, 9–13 июля 2018 г., Прага, Чехия . ЛИПИ. Том. 107. Замок Дагштуль – Центр информатики Лейбница. стр. 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]