Разработка новых методов решения оптимизационных задач приводит к необходимости пересмотра результатов сравнительного анализа методов по быстродействию. В работе [2] представлен генетический алгоритм решения частично целочисленной задачи линейного программирования (ЧЦЗЛП). Кроме того приведены результаты статистического эксперимента, который заключался в сравнительном анализе генетического алгоритма с методом ветвей и границ. Но следует заметить, что в настоящее  время ведутся исследования метода декомпозиции Бендерса, который принадлежит к тому же классу методов, что и рассматриваемые в [2]. Проведем эксперимент и сравним по скорости решения метод декомпозиции Бендерса [1], генетический алгоритм, метод ветвей и границ. Целью сравнительного анализа является ранжирование указанных методов по быстродействию. Для сравнения трех методов используются результаты работы программных реализаций генетического алгоритма, метода ветвей и границ из [2]. Для проведения сравнительного анализа трех методов необходимо было разработать программу на основании метода декомпозиции Бендерса. Программные реализации разрабатывались применительно к ЧЦЗЛП. Рассмотрим постановку этой массовой задачи (1):

10.              Конец

 

 

Сравнительный анализ методов проводился на множестве из трех задач, описанных в электронном каталоге Miplib. Рассматривались задачи "Bell 3a", "lseu" и "p0033", постановка которых в формате mps дана в каталоге Miplib [3]. Указанное множество характеризуется диапазоном размерностей задач от 33 до 133 переменных, диапазоном количества ограничений от 49 до 256 и диапазоном количества целочисленных переменных от 33 до  89. Результаты  работы методов приведены в Табл. 1.  Снимались показания времени решения методами каждой задачи, а также фиксировалось найденное значение целевой функции.

Таблица 1

 

 

Наименование задачи		Метод ветвей и границ	Генетический алгоритм	Метод декомпозиции Бендерса	Оптимальное значение целевой функции
Bell 3a	Время решения, мин.	60,356	36,03	11,33	878430,32
	Найденное значение целевой функции	1458726,68	945512,438	1770182,476
lseu	Время решения, мин.	120	37	2,79	1120
	Найденное значение целевой функции	1441	1120	1017
p0033	Время решения, мин.	0,532	0,853	0,014	3089
	Найденное значение целевой функции	3089	3164	3107

 

 

Примечание. В работе Хоролич производилось 10 запусков метода ветвей и границ для задачи "Bell 3a", что потребовало 36214 секунд. На решение одной задачи в среднем затрачено 

Список литературы

1.     Схрейвер А. Теория линейного и целочисленного программирования / А. Схрейвер, Москва, 1991, Т.2. – С. 602-604.

2.     Хоролич Г.Б. Эволюционные алгоритмы решения задач смешанной целочисленной оптимизации / Г.Б. Хоролич, Красноярск, 2002. – 164 с.

3.     http://miplib.zib.de/miplib3/miplib3/bell3a.mps.gz