Algoritmo para resolver un sistema de inecuaciones lineales sobre los números naturales

Question

Busco un algoritmo para resolver un sistema de inecuaciones lineales de la forma

$$A\,\vec n + \vec c \;\geq\; 0$$

para $\vec n$ donde $A$ es una matriz de enteros, $\vec c$ se compone de números enteros y $\vec n$ de los números naturales (es decir, un algoritmo para encontrar una representación paramétrica de todos los puntos enteros dentro de un politopo convexo en general no acotado).

La solución debería parecerse a la salida del programa de Mathematica Reduce comando, por ejemplo

In[1]:= Reduce[1 - n2 + n3 >= 0 && -1 + n2 >= 0 && -n1 + n2 + n3 >= 0 && n1 - n2 >= 0 && n1 - n3 >= 0 && 1 - n1 + n2 >= 0 && 3 + n2 - n3 >= 0 && n1 >= 0 && n2 >= 0 && n3 >= 0,Integers]
Out[1]= C[1]  Integers && C[1] >= 0 && ((n1 == 3 + C[1] && n2 == 2 + C[1] && n3 == 1 + C[1]) || (n1 == 2 + C[1] && n2 == 1 + C[1] && n3 == 2 + C[1]) || (n1 == 2 + C[1] && n2 == 1 + C[1] && n3 == 1 + C[1]) || (n1 == 1 + C[1] && n2 == 1 + C[1] && n3 == 1 + C[1]) || (n1 == 1 + C[1] && n2 == 1 + C[1] && n3 == C[1]))

(aquí el resultado es una unión de líneas)

o

In[1]:= Reduce[n1 >= 0 && n2 >= 0 && n1 - n2 + 1 >= 0, Integers]
Out[1]= (C[1] | C[2])  Integers && C[1] >= 0 && C[2] >= 0 && ((n1 == C[1] + C[2] && n2 == 1 + C[2]) || (n1 == C[1] + C[2] && n2 == C[2]))

(unión de dos planos)

Nótese que las soluciones describen un número infinito de puntos enteros.

Desafortunadamente, la documentación de Mathematica no menciona qué algoritmo se utiliza.

Estoy portando un paquete existente de Mathematica (usado en física de partículas) por razones de rendimiento a C++. El único ingrediente que falta es un equivalente al Reduce de mando. El algoritmo es necesario para reescribir sumas múltiples de la forma $$ \sum_{n_1=0}^\infty \cdots \sum_{n_N=0}^\infty f(\vec n)\, \theta(\vec a_1\cdot\vec n + \vec c_1) \cdots \theta(\vec a_J\cdot\vec n +\vec c_J) \,,\quad \theta(x)=\begin{cases} 1\;;\; x\geq 0 \\ 0\;;\; x<0 \end{cases} $$ a sumas sin $\theta$ -funciones.

Se agradece cualquier sugerencia.

Answer 1

Por desgracia, este problema es un subconjunto de Programación de números enteros que es NP-Completo, por lo que no encontrará nada necesariamente "eficiente".

Afortunadamente, ahora que sabes el nombre, hay un montón de bibliotecas que tienen heurística de lujo para encontrar soluciones. Conozco lp_solve pero puede elegir uno que sea más apropiado para su proyecto.