Trova i punti interi in un polyhedron

Question

Ciao Abbiamo un poliedro con le disuguaglianze lineari dei suoi confini in n Dimensioni.

.
1. Come trovare il numero di punti interi in questo polyhedron (esattamente o approssimativamente).
2. Come trovare le coordinate dei punti interi in questo polyhedron.

Answer 1

Per darti alcuni termini di ricerca: ciò che descrivi è un enumerazione di fattible solutions a un programma intero .

L'ultima volta che avevo bisogno di qualcosa del genere, non ho trovato una soluzione pronta per l'uso, quindi ho scritto la mia implementazione chiamata " Bande ". Si basa su un algoritmo di ramificazione, utilizzando il motore di programmazione lineare da Coin-o per decidere se il corrispondente Il programma lineare (non integer) ha soluzioni fattibili. Sentiti libero di usarlo che si adatta al tuo bisogno.

Semplicemente determinare il numero dei punti reticoli: credo che ci sia stata una formula per calcolarlo, ma non ricordo alcun dettaglio. Per quanto ricordo, quella formula non era in uso in realtà enumerando le soluzioni.

Guardando Pubblicazioni recenti suggerisce che potresti voler avere un Guarda latte .

Answer 2

Software Apeing in grado di calcolare i punti interi di un dato poliedro (tra lo scafo convesso) è Porta .

Tuttavia, tutti i software relativi a questa base del problema sulle enumerazioni, in modo tale da non riescono a modelli più grandi.

Cordiali saluti