Базис Гильберта (линейное программирование)

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

Определение

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

Учитывая решетку $L\subset \mathbb {Z} ^{d}$ и выпуклый многогранный конус с образующими $a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{d}$

$C=\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}\in \mathbb {R} \}\subset \mathbb {R} ^{d},$

мы рассматриваем моноид $C\cap L$. По лемме Гордана этот моноид конечно порождён, т. е. существует конечное множество точек решётки $\{x_{1},\ldots ,x_{m}\}\subset C\cap L$ такая, что каждая точка решетки $x\in C\cap L$ представляет собой целую коническую комбинацию этих точек:

$x=\lambda _{1}x_{1}+\ldots +\lambda _{m}x_{m},\quad \lambda _{1},\ldots ,\lambda _{m}\in \mathbb {Z} ,\lambda _{1},\ldots ,\lambda _{m}\geq 0.$

Конус С называется заостренным, если $x,-x\in C$ подразумевает $x=0$. В этом случае существует единственный минимальный порождающий набор моноида $C\cap L$— гильбертовский базис C . Он задается набором неприводимых точек решетки: элемент $x\in C\cap L$ называется неприводимым, если его нельзя записать в виде суммы двух ненулевых элементов, т. е. $x=y+z$ подразумевает $y=0$ или $z=0$.

Ссылки

• Брунс, Винфрид; Губеладзе, Иосиф; Хенк, Мартин; Мартин, Александр; Вейсмантель, Роберт (1999), «Контрпример к целочисленному аналогу теоремы Каратеодори», Журнал чистой и прикладной математики , 1999 (510): 179–185, doi : 10.1515/crll.1999.045
• Кук, Уильям Джон; Фонлупт, Жан; Шрийвер, Александр (1986), «Целый аналог теоремы Каратеодори», Журнал комбинаторной теории, серия B , 40 (1): 63–70, doi : 10.1016/0095-8956(86)90064-X
• Эйзенбранд, Фридрих; Шмонин, Геннадий (2006), «Оценки Каратеодори для целочисленных конусов» , Operations Research Letters , 34 (5): 564–568, doi : 10.1016/j.orl.2005.09.008
• Д.В. Пасечник (2001). «О вычислении базисов Гильберта с помощью алгоритма Эллиотта — Мак-Магона» . Теоретическая информатика . 263 (1–2): 37–46. дои : 10.1016/S0304-3975(00)00229-2 . HDL : 10220/8240 .