Основа Грейвера

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

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

Базис Грейвера целочисленной матрицы 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) и их отрицаний.

Решение целочисленного программирования с использованием базисов Грейвера

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

$\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-трудной и, следовательно, предположительно не может быть решена за полиномиальное время.

Однако базис Грейвера $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\}$

можно решить, используя базис Грейвера $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 -кратное целочисленное программирование,
• N -кратное 4-блочное разложимое целочисленное программирование,
• кластеризация,
• контроль раскрытия информации в статистических базах данных,
• и справедливое распределение неделимых объектов.

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

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

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

Иерархия аппроксимаций целочисленного программирования

Обозначим через $G(m,n)$ основа матрицы Грейвера $A$ определяя универсальную задачу таблицы 3 × m × n , обсуждавшуюся выше. Элементы $G(m,n)$ представляют собой таблицы размером 3 × m × n , у которых суммы всех строк равны 0. Типом такой таблицы является количество ее ненулевых размером 3 × m слоев . Оказывается, существует конечная функция сложности Грейвера g ( m ) такая, что для любого n тип любого элемента базиса Грейвера $G(m,n)$ не превышает г ( м ). Отсюда следует, что базис Грейвера $G(m,n)$ это союз ${n \choose g(m)}$ соответствующим образом встроенные копии базиса Грейвера $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 в $G(A)$ без явного построения базиса Грейвера , в кубическом времени $O\left(n^{3}\right)$ независимо от системы. В терминологии параметризованной сложности это означает, что все эти проблемы, параметризованные соответствующим образом, и, в частности, табличные задачи l × m × n , параметризованные l и m , являются управляемыми с фиксированным параметром .

См. также

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