Найти целые точки в многограннике
Здравствуйте, у нас есть многогранник с линейными неравенствами его границ в n измерениях.
- Как найти количество целых точек в этом многограннике (точно или приблизительно).
- как найти координаты целых точек в этом многограннике.
2 ответа
Чтобы дать вам несколько поисковых терминов: вы описываете перечень возможных решений целочисленной программы.
В прошлый раз мне нужно было что-то вроде этого, я не мог найти готовое к использованию решение, поэтому я написал свою собственную реализацию под названием " bande". Он основан на алгоритме ветвления, использующем механизм линейного программирования от COIN-OR, чтобы решить, имеет ли соответствующая линейная (нецелочисленная) программа какие-либо возможные решения. Не стесняйтесь использовать, что это соответствует вашим потребностям.
Что касается простого определения количества точек решетки: я думаю, что была какая-то формула для ее вычисления, но я не помню никаких деталей. Насколько я помню, эта формула не использовалась для фактического перечисления решений.
Просмотр последних публикаций показывает, что вы можете взглянуть на LattE.
Программное обеспечение, способное вычислять целочисленные точки заданного многогранника (среди выпуклых оболочек), является портом.
Тем не менее, все программное обеспечение, касающееся этой проблемы, основано на перечислениях, так что оно не подходит для более крупных моделей.
С наилучшими пожеланиями