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

Математическая задача оптимизации, ограниченная целыми числами

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

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

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

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

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

${\displaystyle {\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 в стандартной форме выражается как

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

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

Пример

IP-политоп с релаксацией LP

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

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

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

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

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

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

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

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

Варианты

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

Линейное программирование от нуля до единицы (или двоичное целочисленное программирование ) включает в себя задачи, в которых переменные ограничены либо 0, либо 1. Любая ограниченная целочисленная переменная может быть выражена как комбинация двоичных переменных . ^[5] Например, если задана целочисленная переменная, , переменная может быть выражена с помощью двоичных переменных: ${\displaystyle 0\leq x\leq U}$ ${\displaystyle \lfloor \log _{2}U\rfloor +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.

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

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

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

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

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

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

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

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

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

Сотовые сети

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

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

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

Алгоритмы

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

Используя полную унимодулярность

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

Так как столбцы линейно независимы и квадратны, невырождены, и, следовательно, по предположению, унимодулярны и, следовательно , . Кроме того, так как невырождены, они обратимы и, следовательно , . По определению, . Здесь обозначает сопряженное число и является целым числом, поскольку является целым числом. Следовательно, Таким образом, если матрица ILP полностью унимодулярна, вместо использования алгоритма ILP можно использовать симплексный метод для решения релаксации LP, и решение будет целочисленным. ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \det(B)=\pm 1}$ ${\displaystyle B}$ ${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$ ${\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}$ ${\displaystyle B^{\mathrm {adj} }}$ ${\displaystyle B}$ ${\displaystyle B}$ $${\displaystyle {\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}}}$$ ${\displaystyle A}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. Карп, Ричард М. (1972). «Сводимость среди комбинаторных задач» (PDF) . В RE Miller; JW Thatcher; JD Bohlinger (ред.). Сложность компьютерных вычислений . Нью-Йорк: Plenum. стр. 85–103. doi :10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.
2. "Смешанно-целочисленное линейное программирование (MILP): формулировка модели" (PDF) . Получено 16 апреля 2018 г.
3. Papadimitriou, CH ; Steiglitz, K. (1998). Комбинаторная оптимизация: алгоритмы и сложность . Mineola, NY: Dover. ISBN 0486402584.
4. Эриксон, Дж. (2015). "Сокращение целочисленного программирования" (PDF) . Архивировано из оригинала (PDF) 18 мая 2015 г.
5. Уильямс, HP (2009). Логическое и целочисленное программирование . Международная серия по исследованию операций и науке управления. Том 130. ISBN 978-0-387-92280-5.
6. Борндорфер, Р.; Грётшель, М. (2012). «Проектирование телекоммуникационных сетей методом целочисленного программирования» (PDF) .
7. Шарма, Дипак (2010). «Планирование частот».
8. Мораис, Хьюго; Кадар, Питер; Фариа, Педро; Вейл, Зита А.; Ходр, Ее Величество (1 января 2010 г.). «Оптимальное планирование возобновляемой микросети в изолированной зоне нагрузки с использованием смешанно-целочисленного линейного программирования». Возобновляемая энергия . 35 (1): 151–156. Бибкод : 2010REne...35..151M. doi :10.1016/j.renene.2009.02.031. hdl : 10400.22/1585 . ISSN  0960-1481.
9. Ому, Акомено; Чоудхари, Ручи; Бойес, Адам (2013-10-01). «Оптимизация распределенной системы энергоресурсов с использованием смешанного целочисленного линейного программирования». Энергетическая политика . 61 : 249–266. Bibcode : 2013EnPol..61..249O. doi : 10.1016/j.enpol.2013.05.009. ISSN  0301-4215. S2CID  29369795.
10. Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). «Результаты внедрения и летных испытаний наведения БПЛА на основе MILP». 2005 IEEE Aerospace Conference . С. 1–13. doi :10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID  13447718.
11. Радманеш, Мохаммадреза; Кумар, Маниш (2016-03-01). «Формирование полета БПЛА в присутствии движущихся препятствий с использованием быстрого динамического смешанного целочисленного линейного программирования». Аэрокосмическая наука и технологии . 50 : 149–160. Bibcode : 2016AeST...50..149R. doi : 10.1016/j.ast.2015.12.021 . ISSN  1270-9638.
12. Баст, Ханна; Брози, Патрик; Сторандт, Сабина (2017-10-05). «Эффективное создание географически точных транзитных карт». arXiv : 1710.02226 [cs.CG].
13. Скарф, Герберт Э. (1981). «Производственные множества с неделимостью, часть I: общие положения». Econometrica . 49 (1): 1–32. doi :10.2307/1911124. ISSN  0012-9682. JSTOR  1911124.
14. Lenstra, HW (1983-11-01). «Целочисленное программирование с фиксированным числом переменных». Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. ISSN  0364-765X. 
15. Амента, Нина ; Де Лоера, Хесус А.; Соберон, Пабло (2017). «Теорема Хелли: новые вариации и приложения». В Харрингтоне, Хизер А .; Омар, Мохамед; Райт, Мэтью (ред.). Труды специальной сессии AMS по алгебраическим и геометрическим методам в прикладной дискретной математике, состоявшейся в Сан-Антонио, штат Техас, 11 января 2015 г. Contemporary Mathematics. Том 685. Провиденс, Род-Айленд: Американское математическое общество. стр. 55–95. arXiv : 1508.07606 . doi : 10.1090/conm/685. ISBN 9781470423216. МР  3625571.
16. Каннан, Рави (1 августа 1987 г.). «Теорема Минковского о выпуклом теле и целочисленное программирование». Математика исследования операций . 12 (3): 415–440. doi :10.1287/moor.12.3.415. ISSN  0364-765X. S2CID  495512.
17. Goemans, Michel X. ; Rothvoss, Thomas (2020-11-07). «Полиномиальность для упаковки в контейнеры с постоянным числом типов элементов». Journal of the ACM . 67 (6): 38:1–38:21. doi : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN  0004-5411. S2CID  227154747.
18. Франк, Андраш; Тардос, Эва (1987-03-01). «Применение одновременной диофантовой аппроксимации в комбинаторной оптимизации». Combinatorica . 7 (1): 49–65. doi :10.1007/BF02579200. ISSN  1439-6912. S2CID  45585308.
19. Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). «Сложность эффективного и свободного от зависти распределения ресурсов: несколько агентов, ресурсов или уровней полезности». Труды Двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
20. Бредерек, Роберт; Качмарчик, Анджей; Кноп, Душан; Нидермейер, Рольф (17.06.2019). «Справедливое распределение с высокой множественностью: Lenstra, усиленная N-кратным целочисленным программированием». Труды конференции ACM 2019 года по экономике и вычислениям . EC '19. Финикс, Аризона, США: Ассоциация вычислительной техники. стр. 505–523. doi :10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID  195298520.
21. Дадуш, Дэниел (14.06.2012). «Целочисленное программирование, решетчатые алгоритмы и детерминированная оценка объема».
22. Рейс, Виктор; Ротвосс, Томас (2023-03-26). «Гипотеза о плоскостности подпространства и более быстрое целочисленное программирование».
23. Хильдебранд, Роберт (2016-10-07). "Алгоритм FPT для смешанной целочисленной программы". Theoretical Computer Science Stack Exchange . Получено 2024-05-21 .
24. Гловер, Ф. (1989). «Поиск с запретом — Часть II». Журнал ORSA по вычислениям . 1 (3): 4–32. doi :10.1287/ijoc.2.1.4. S2CID  207225435.
25. Коутецкий, Мартин; Левин, Асаф; Онн, Шмуэль (2018). «Параметризованный сильно полиномиальный алгоритм для блочно-структурированных целочисленных программ». В Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (ред.). 45-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2018, 9–13 июля 2018 г., Прага, Чешская Республика . LIPIcs. Том 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. стр. 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .

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

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

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

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