Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/int_m/int_m4.htm
Дата изменения: Wed Oct 8 16:21:54 2014
Дата индексирования: Sat Apr 9 23:17:29 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. Математическое программирование. Рекомендации по использованию

6. Задачи целочисленного программирования

Подпрограмма MNR3R, реализующая алгоритм Балаша для линейной задачи с булевыми переменными, компактно хранит входную и промежуточную информацию. При длительном счете можно выдать промежуточный результат, а потом продолжить счет, передав в программу последнее допустимое решение. Удачное допустимое решение известное apriory может существенно ускорить счет.

Полностью целочисленный алгоритм Гомори, реализованный в подпрограмме MLC2R, предназначен для решения линейных задач целочисленного программирования с большим количеством ненулевых элементов в матрице условий (больше 50%). Он требует довольно большого объема памяти и поэтому размеры решаемых задач довольно жестко ограничены: (4 + m + n) (n + 3) ≤ 10000, где  m - количество ограничений, а  n - количество переменных в матрице условий.

Для задач с разреженной матрицей условий в подпрограмме MLC3R реализован модифицированный вариант алгоритма Гомори. В этой программе матрица условий хранится компактно, программа требует меньше памяти, и в случае сильной разреженности матрицы условий время счета (по сравнению с MLC2R) тоже уменьшается.