Base de Hilbert (programación lineal)

La base de Hilbert de un cono convexo C es un conjunto mínimo de vectores enteros tal que cada vector entero en C es una combinación cónica de los vectores en la base de Hilbert con coeficientes enteros.

Definición

Visualización de la base de Hilbert

Dada una red y un cono poliédrico convexo con generadores ${\displaystyle L\subset \mathbb {Z} ^{d}}$ ${\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{d}}$

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

consideramos el monoide . Según el lema de Gordan , este monoide se genera de forma finita, es decir, existe un conjunto finito de puntos de la red tal que cada punto de la red es una combinación cónica entera de estos puntos: ${\displaystyle C\cap L}$ ${\displaystyle \{x_{1},\ldots ,x_{m}\}\subset C\cap L}$ ${\displaystyle x\in C\cap L}$

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

El cono C se llama puntiagudo si implica . En este caso existe un conjunto generador mínimo único del monoide : la base de Hilbert de C. Está dado por el conjunto de puntos de la red irreducibles: un elemento se llama irreducible si no puede escribirse como la suma de dos elementos distintos de cero, es decir, implica o . ${\displaystyle x,-x\in C}$ ${\displaystyle x=0}$ ${\displaystyle C\cap L}$ ${\displaystyle x\in C\cap L}$ ${\displaystyle x=y+z}$ ${\displaystyle y=0}$ ${\displaystyle z=0}$

Referencias

• Bruns, Winfried; Gubeladze, José; Henk, Martín; Martín, Alejandro; Weismantel, Robert (1999), "Un contraejemplo de un análogo entero del teorema de Carathéodory", Journal für die reine und angewandte Mathematik , 1999 (510): 179–185, doi :10.1515/crll.1999.045
• Cocinero, William John; Fonlupt, Jean; Schrijver, Alexander (1986), "Un análogo entero del teorema de Carathéodory", Journal of Combinatorial Theory, Serie B , 40 (1): 63–70, doi : 10.1016/0095-8956(86)90064-X
• Eisenbrand, Friedrich; Shmonin, Gennady (2006), "Límites de Carathéodory para conos enteros", Operations Research Letters , 34 (5): 564–568, doi :10.1016/j.orl.2005.09.008
• DV Pasechnik (2001). "Sobre el cálculo de las bases de Hilbert mediante el algoritmo de Elliott-MacMahon". Informática Teórica . 263 (1–2): 37–46. doi : 10.1016/S0304-3975(00)00229-2 . hdl : 10220/8240 .