Trouvez les points entier dans un polyèdre

Question

Bonjour Nous avons un polyèdre avec les inégalités linéaires de ses limites en n dimensions.

1. Comment trouver le nombre de points entier dans ce polyèdre (exactement ou approximativement).
2. Comment trouver les coordonnées des points d'entier dans ce polyèdre.

Answer 1

Pour vous donner des termes de recherche: ce que vous décrivez est un énumération de solutions réalisables à un programme entier .

La dernière fois que j'ai eu besoin de quelque chose comme ça, je ne pouvais pas trouver une solution prête à l'emploi, alors j'ai écrit ma propre implémentation appelée " bande ". Il est basé sur un algorithme de branchement, à l'aide du moteur de programmation linéaire de Coin-ou pour décider si le correspondant Le programme linéaire (non entier) a des solutions réalisables. N'hésitez pas à utiliser qu'il convient à votre besoin.

Pour déterminer simplement le numéro de points de réseau: je pense qu'il y avait une formule pour calculer cela, mais je ne me souviens pas de détails. Autant que je me souvienne, cette formule n'était pas utilisée pour énumérer réellement les solutions.

regarder Publications récentes suggère de vouloir avoir un Regardez Latte .

Answer 2

Software Beeing Capable de calculer les points entier d'un polyèdre donné (parmi la coque convexe) est PORTA .

Cependant, tous les logiciels concernant cette base de problèmes sur des énumérations, de sorte qu'il échoue à des modèles plus importants.

meilleures salutations