целочисленное линейное программирование
Один из самых эффективных алгоритмов — branch-and-cut
Отсекающие плоскости строятся по методу Гомори
Скорость работы критически зависит от следующих факторов:
1) когда заканчивать метод отсечений и перейти к ветвлению;
2) выбор правой или левой ветви (существует ряд эвристик).
Я лично использовал следующие параметры:
отсечение заканчивается, когда размер задачи увеличивается в 2 раза;
выбор ветви (левая или правая) — случайный алгоритм.
В результате — алгоритм неплохо работает даже для неограниченных задач например:
1 <= 10*x + 20*y - 30*z <= 9,
x, y, z - integer
Отсекающие плоскости строятся по методу Гомори
Скорость работы критически зависит от следующих факторов:
1) когда заканчивать метод отсечений и перейти к ветвлению;
2) выбор правой или левой ветви (существует ряд эвристик).
Я лично использовал следующие параметры:
отсечение заканчивается, когда размер задачи увеличивается в 2 раза;
выбор ветви (левая или правая) — случайный алгоритм.
В результате — алгоритм неплохо работает даже для неограниченных задач например:
1 <= 10*x + 20*y - 30*z <= 9,
x, y, z - integer
Если нужно попроще в понимании — то обычный branch-and-bound, но он не останавливается для неограниченных задач (см. пример выше)
спасибо
зы: хз, чо я в карренте создал, а не в стади, можно снести)
зы: хз, чо я в карренте создал, а не в стади, можно снести)
Оставить комментарий
Happysad
есть симплекс, задаваймый системой из n неравенств, подскажите алгоритм, который ищет целочисленную точку внутри симплекса и соответственно останавливается, если таковой нетжелательно попроще в понимании, на время работы забить