целочисленное линейное программирование, подскажите алгоритм

evor

собственно, нужно проверить симплекс (не более чем n-1 - мерный) на наличие целочисленной точки
где почитать про алгоритмы?

Maria-mirabella

кажется, должно помочь:
Пападимитриу, Стайглиц "Комбинаторная оптимизация"
http://narod.ru/disk/43416491001.687a7628ea7f5634f55840157d6...

evor

Пападимитриу, Стайглиц "Комбинаторная оптимизация"
спасибо, попробую почитать, может кто знает вкратце, существуют полиномиальные алгоритмы?
а то у меня одна ветка задачи вот в такую упёрлась, раньше не сталкивался

Lokomotiv59

Еще можно на википедии. Основные алгоритмы:
 Branch_and_bound
 Branch_and_cut
 Cutting_plane
и далее по ссылкам можно походить
PS. Вот еще полезный ресурс: http://branchandcut.org/faq.htm

Lokomotiv59

существуют полиномиальные алгоритмы
Проверка наличия целой точки внутри симплекса — это NP-полная задача.
Оставить комментарий
Имя или ник:
Комментарий: