Программа решения задач о покрытии множеств

Назначение - Решение задач о покрытии множеств

Используемый алгоритм - метод ветвей и границ с определениеи  нижних, верхних границ  на основе приближенного решения двойственных задач с помощью субградиентного метода. Для сокращения размерности по исходным и двойственным переменным используются логические процедуры. Логическое тестирование осуществляется в каждом узле дерева ветвей и границ.  В процедуре ветвления в качестве входных данных используется вектор двойственных оценок, полученный на предшествующем уровне. Для ветвления в начале выбирается строка, соответсвующая максимальной компоненте вектора двойстенных оценок. Столбцы в выбранной строке упорядычиваются по возрастанию их приведенной стоймости.  Для просмотра индексов по столбцам и строкам используются разреженные строчный и столбцовый форматы. При этом  создаются только массивы индексов, а для элементов матрицы нет необходимости отводить память [1]. 

[1]     Забиняко Г.И. Реализация алгоритмов решения задачи о покрытии множеств и анализ их эффективности // Вычислительные технологии -2007,Т.12,№6, с.50-58.                      

Разработаны  варианты программ в однопроцессорном и многопроцессорном режимах.                                         

Функциональные возможности - реально с обоснованием оптимальности решаются задачи с числом строк до 500 и столбцов до 5000.
Инструментальные средства создания - фортран, MPI