encontrar os pontos inteiros em um poliedro

Question

Olá, temos um poliedro com as desigualdades lineares de seus limites em n dimensões.

1. como encontrar o número de pontos inteiros neste poliedro (exatamente ou aproximadamente).
2. como encontrar as coordenadas dos pontos inteiros neste poliedro.

Answer 1

Para fornecer alguns termos de pesquisa:o que você descreve é ​​um enumeração de soluções viáveis para um programa inteiro.

Da última vez que precisei de algo assim, não consegui encontrar uma solução pronta para uso, então escrevi minha própria implementação chamada “banda”.É baseado em um algoritmo de ramificação, usando o mecanismo de programação linear do MOEDA-OU para decidir se o programa linear (não inteiro) correspondente tem alguma solução viável.Sinta-se à vontade para usá-lo de acordo com sua necessidade.

Quanto à simples determinação número de pontos da rede:Acredito que havia alguma fórmula para calcular isso, mas não me lembro de nenhum detalhe.Pelo que me lembro, essa fórmula não servia para enumerar as soluções.

Olhando para publicações recentes sugere que você pode querer dar uma olhada Café com leite.

Answer 2

Abeguração de software capaz de calcular os pontos inteiros de um determinado poli -edron (entre o casco convexo) é Porta .

No entanto, todo o software relativo a esta base de problemas em enumerações, de modo que ele falhe para modelos maiores.

Melhores cumprimentos