Encuentra los puntos enteros en un poliedro.

Question

Hola, tenemos un poliedro con las desigualdades lineales de sus límites en n dimensiones.

1. Cómo encontrar el número de puntos enteros en este poliedro (exactamente o aproximadamente).
2. Cómo encontrar las coordenadas de los puntos enteros en este poliedro.

Answer 1

Para darle algunos términos de búsqueda: lo que describe es una enumeración de Soluciones factibles a un programa entero

La última vez que necesitaba algo como esto, no pude encontrar una solución lista para usar, así que escribí mi propia implementación llamada " bande ". Se basa en un algoritmo de ramificación, utilizando el motor de programación lineal de coin-o para decidir si corresponde El programa lineal (no entero) tiene cualquier solución factible. Siéntase libre de usar que se adapte a su necesidad.

Como para determinar simplemente el número de los puntos de celosía: creo que hubo alguna fórmula para calcular eso, pero no recuerdo ningún detalle. Por lo que recuerdo, esa fórmula no era de uso en enumerar las soluciones.

mirando a Publicaciones recientes sugiere que es posible que desee tener un Mira a Latte .

Answer 2

Software Peating Poder de calcular los puntos enteros de un poliedro dado dado (entre el casco convexo) es Porta .

Sin embargo, todo el software relativo a esta base de problemas en las enumeraciones, de modo que falla para modelos más grandes.

mejor saludos