Граверная основа

В прикладной математике более серьезные основания позволяют итеративным решениям линейных и различных нелинейных целочисленного программирования задач в полиномиальное время . Они были представлены Джеком Э. Грейвером . Их связь с теорией баз Грёбнера обсуждалась Берндом Штурмфелем . Алгоритмическая теория Граверных Баз и ее применение для целочисленного программирования описывается Шмуэлем Онн .

Формальное определение

Груверная основа матрицы M × N целочисленной $A$ это конечный набор $G(A)$ минимальных элементов в наборе

$\{x\in \mathbb {Z} ^{n}:Ax=0,\ x\neq 0\}\,$

под хорошо частичным порядком на $\mathbb {Z} ^{n}$ определяется $x\sqsubseteq y$ когда $x_{i}y_{i}\geq 0$ и $|x_{i}|\leq |y_{i}|$ для всех я. Например, более серьезная основа $A=(1,2,1)$ состоит из векторов (2, -1,0), (0, -1,2), (1,0, -1), (1, -1,1) и их отрицания.

Решение целочисленного программирования с использованием Graver Bases

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

$\min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .$

Это одна из наиболее фундаментальных проблем с дискретной оптимизацией и обладает очень широкой модельной мощностью и многочисленными приложениями в различных областях, но, как правило, очень жестко вычислительно вычисляется. Однако, учитывая серьезную основу $G(A)$ из $A$Проблема с линейными и различными нелинейными объективными функциями может быть решена в полиномиальное время, как объяснено дальше.

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

Самый изученный случай, тщательно обработанный в, является линейным целочисленным программированием ,

$\min\{wx\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .$

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

Тем не менее, серьезная основа $G(A)$ из $A$ имеет следующее свойство. Для каждой возможной точки x :

• Любой x оптимален (т.е. минимизирует $w\cdot x$ Учитывая ограничения);
• Или существует вектор g в $G(A)$, так что x + g возможна и $w\cdot (x+g)<w\cdot x$ (т.е. X можно улучшить, добавив к нему элемент граверной основы).

Поэтому, учитывая более серьезную основу $G(A)$, ILP может быть решена в полиномиальное время, используя следующий простой итеративный алгоритм. какая -то начальная возможная точка x Предположим сначала, что дана . Пока это возможно, повторите следующую итерацию: найдите положительное целое число Q и элемент G в $G(A)$ Такой, что X + QG не нарушает границы и дает наилучшее возможное улучшение; Обновление x : = x + qg и перейдите к следующей итерации. Последняя точка X является оптимальным, а количество итераций является полиномом.

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

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

Обращаясь к случаю общих целевых функций F , если переменные не ограничены, то проблема может быть неожиданной: она следует из решения 10 -й проблемы Гилберта (см. ), что не существует алгоритма, который, с учетом целочисленного многочлена F градуса 8 в 58 переменных, решает, является ли минимальное значение f по всем 58-мерным целочисленным векторам 0. Однако, когда переменные ограничены, проблема

$\min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}$

может быть решено с помощью Graver Bouse $G(A)$ в полиномиальное время для несколько нелинейных целевых функций, включая :

• Разделимые функции формы $f(x)=\sum _{i=1}^{n}f_{i}(x_{i})$;
• В частности, P-форма $f(x)=\|x\|_{p}$ Для каждого положительного целого числа P ;
• составной констатки Функции f ( x ) = g ( wx ), где w представляет собой целочисленную матрицу D × n с фиксированной D , и где G -D -вежливая вогнутая функция;
• Определенные (в)-определенные квадратичные и более высокие полиномиальные функции.

Некоторые приложения

Многомерные таблицы

Рассмотрим следующую задачу оптимизации в течение трехмерных таблиц с предписанной линейной суммой,

$\min\{wx\ :\ x\in {\mathbb {Z} }_{+}^{l\times m\times n}\,,\ \sum _{i}x_{i,j,k}=a_{j,k}\,,\ \sum _{j}x_{i,j,k}=b_{i,k}\,,\ \sum _{k}x_{i,j,k}=c_{i,j}\}\ ,$

с $a_{j,k}$, $b_{i,k}$, $c_{i,j}$ Неотрицательные целые числа (максимальное значение которого неявно ограничивает все переменные сверху). Обозначайте $A$ ( LM + LN + MN ) × ( LMN ) определяющая матрицу этой системы. Обратите внимание, что эта матрица, как правило, не является совершенно немодулярной . Тем не менее, это было показано в что для каждого фиксированного L и M , его более серьезная основа $G(A)$ может быть вычислен во времени, который является полиномом в n . Результаты, упомянутые выше, позволяют затем решить эту проблему в полиномиальное время для фиксированного L и M и переменной n . Обратите внимание, что если только одна сторона L таблицы зафиксирована (даже с L = 3), в то время как как M, так и N являются переменными, то проблема жестко NP, как показано в. В целом, аналогичные положительные результаты сохраняются для проблем с более высокой таблицей (представленные в ): для каждого фиксированного D и $m_{1},\dots ,m_{d}$, (не) -линейная оптимизация над $m_{1}\times \cdots \times m_{d}\times n$ Таблицы с переменной n и предписанными краями могут быть выполнены в полиномиальное время. Это имеет дальнейшие приложения к задачам безопасности и конфиденциальности в статистических базах данных .

Многородные потоки

Рассмотрим задачу целочисленного многопромочного потока по маршрутизации k типов целочисленных товаров от M поставщиков до N потребителей, подверженных предложению, потреблению и ограничениям емкости, чтобы минимизировать сумму линейных или затравных затрат на выпуклость на дуги. Затем для каждого фиксированного k и m можно рассчитать более серьезную основу определяющей системы и полученная целевая функция Минимизирован во времени, который является полиномом в переменном числе N потребителей и в остальных данных.

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

Многие применения алгоритмической теории Граверных Баз также включают:

• Стохастическое целочисленное программирование,
• N -Fold Integer Programming,
• N -Fold 4 -Block Decomposable Integer Programming,
• кластеризация,
• управление раскрытием в статистических базах данных,
• и справедливое распределение неделимых объектов.

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

Универсальность и параметризация

Это было показано в что каждая (ограниченная) задача целочисленного программирования точно эквивалентна задаче таблицы 3 × N , обсуждаемой выше для некоторых M и N и некоторых сумм строк. Таким образом, такие 3 × M × N проблемы таблицы являются универсальными для целочисленного программирования. Более того, для каждого фиксированного M полученный класс целочисленных программ может быть решен в полиномиальное время с помощью итеративного метода Graver Base, описанного выше. Таким образом, ширина таблицы M обеспечивает параметризацию всех задач целочисленного программирования.

Иерархия приближения для целочисленного программирования

Обозначайте $G(m,n)$ Груверная основа матрицы $A$ Определение универсальной задачи таблицы 3 × m × n , обсуждаемой выше. Элементы $G(m,n)$ таблицы 3 × м × n со всеми суммами строк, равными 0. Тип такой таблицы - это количество его ненулевых 3 -м слоев . Оказывается, что существует конечная более серьезная функция сложности g ( m ), так что для любого n тип любого элемента Грейв. $G(m,n)$ больше всего g ( m ). Отсюда следует, что более серьезная основа $G(m,n)$ это союз ${n \choose g(m)}$ соответствующим образом встроенные копии Graver Bouse $G(m,g(m))$Полем Чтобы приблизительно решить на практике произвольную проблему целочисленного программирования, выполните следующее. Сначала введите его в подходящую задачу 3 × m × n таблицы, как это включено универсальностью, отмеченной выше. Теперь примените следующую иерархию приближения $G(m,n)$Полем На уровне K этой иерархии, пусть $G_{k}(m,n)$ быть подмножеством $G(m,n)$ состоящий только из этих элементов типа не более k ; Используйте это приближение $G_{k}(m,n)$ в итерационном алгоритме как можно дольше, чтобы получить максимально хорошую возможную точку для задачи целочисленного программирования, встроенной в задачу таблицы 3 × M × N ; Если целевая функция значения этой точки является удовлетворительным (скажем, по сравнению со значением линейной релаксации программирования ), то используйте эту точку; в противном случае увеличить k и перейти к следующему уровню иерархии. Это можно показать что для любого фиксированного уровня k , приближение $G_{k}(m,n)$ Граверной основы имеет полиномиальную кардинальность $O\left(m^{g(k)}n^{k}\right)$ и может быть рассчитан за это много времени.

Фиксированная параметр трактативность: от многочлена до кубической сложности времени

Временная сложность решения некоторых приложений, обсуждаемых выше, таких как многомерные задачи таблицы, проблемы с множественным потоком и n -распадные задачи программирования, в котором преобладает кардинальность соответствующей Гравере, которая является полиномом. $O\left(n^{g}\right)$ с типично большой степенью g, которая является подходящей грубой сложностью системы. В Представлен гораздо более быстрый алгоритм, который находит на каждой итерации лучшее улучшение x + qg с q положительным целым числом и g element в $G(A)$ без явного построения более серьезной основы , в кубическое время $O\left(n^{3}\right)$ независимо от системы. В терминологии параметризованной сложности это подразумевает, что все эти проблемы соответственно параметризованы, и, в частности, проблемы с таблицей L × M × N , параметризованные L и M , являются фиксированными параметрами .

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

• Лемма Гордана - еще один инструмент, связанный с нулевыми наборами целочисленных матриц.