Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Колосов, Антон Павлович

• Колосов, Антон Павлович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Колосов, Антон Павлович

Введение

1 Некоторые методы анализа и решения задач целочисленного программирования

1.1 Постановки задач.

1.2 L - разбиение и его свойства.

1.3 Метод перебора L - классов

1.4 Двойственные дробные алгоритмы отсечения

1.5 Унимодулярные преобразования.

2 Построение оценок числа итераций

2.1 Анализ алгоритмов для семейств задач на плоскости.

2.2 Оценки числа итераций алгоритмов в n-мерном случае

2.3 О выборе производящей строки в первом алгоритме Гомори.

3 Исследование вопросов устойчивости алгоритмов

3.1 О неустойчивости некоторых алгоритмов отсечения.

3.2 Зависимость числа итераций первого алгоритма Гомори от целевой функции.

4 Алгоритмы перебора ^-классов для задачи планирования производства с интервальными данными

4.1 Дискретная задача планирования производства с интервальными данными.

4.2 Алгоритм перебора L - классов.

4.3 Алгоритмы приближенного решения задачи.

4.4 Экспериментальные исследования.

Введение диссертации (часть автореферата) на тему «Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения»

Актуальность темы. Исследование и решенне многих задач, возникающих в экономике, планировании, технике и других областях, ввиду их сложности осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного линейного программирования (ЦЛП). Условие цело численности позволяет учесть такие факторы, как неделимрсть объектов, дискретность процессов, наличие альтернатив, фиксированные доплаты и ряд других. Значительный интерес к задачам целочисленного программирования обусловлен их NP-трудпо-стыо [7].

Актуальность исследования задач ЦЛП связана также с* тем, что модели и методы целочисленного программирования широко используются для анализа и решения различных классов задач дискретной оптимизации [3,15,20,26,66,67], например, планирования производства, оптимального размещения [4,5,23,38,57], оптимизации на графах, развозки продукции, о покрытии [64], об упаковке [36,56], выполнимости и максимальной выполнимости [1,30,31], задач проектирования с логическими ограничениями [39]. В работах [40,41] описаны параллельные алгоритмы для решения задачи выполнимости на базе моделей ЦЛП.

В настоящее время проблематика целочисленного программирования (ЦП) явл51ется достаточно широкой и включает исследование структуры и сложности решения задач, разработку и применение методов ветвей и границ, отсечения, декомпозиции, полиэдрального подхода, приближенных и гибридных алгоритмов, изучение устойчивости задач и алгоритмов, многокритериальные постановки и ряд других [2,6,8,21,22,28,29,33,35,38,

44,45,47,48,52,53, 58,61, 64, 68,70-73, 75, 79-83,85,98,99]. Во' многих алгоритмах используется аппарат непрерывной оптимизации [20,28,48,62,70]. С теоретической точки зрения алгоритмы ЦЛП по ряду направлений исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций [36], построения семейств трудных задач, устойчивости алгоритмов при малых изменениях исходных данных [17,18], поиск унимодулярных преобразований пространства, позволяющих улучшать L - структуру задач и повышать эффективность алгоритмов [34].

В области ЦП широкое применение получил подход, предложенный А. А. Колоколовым, который основан на использовании регулярных разбиений евклидова пространства [28], в том числе, Zr-разбиения. С использованием этого подхода, в [8,22,28,29,33,35,68,81,91] и других работах были построены верхние и нижние оценки числа итераций для ряда алгоритмов, введены новые классы отсечений, получены результаты по устойчивости задач и алгоритмов дискретной оптимизации, исследована L - структура задач. Предложен метод перебора L — классов [28,29], на основе которого были разработаны алгоритмы решения задачи о покрытии, задачи о рюкзаке, задач выполнимости и максимальной выполнимости и ряда других.

Многие методы решения задач ЦП основаны на использовании релаксационных множеств, определяемых системой ограничений, получающейся из исходной исключением условия целочисленности переменных. Важную роль играет так называемое дробное накрытие задачи. Оно состоит из всех точек, лежащих между лексикографически оптимальными решениями задачи ЦП и соответствующей ей непрерывной задачи. «Объем» данного множества в значительной мере определяет сложность задачи. Регулярные разбиения позволяют измерить этот «объем» . Как правило, задачи с мощными в терминах регулярных разбиений дробными накрытиями более трудны для решения. Перспективным направлением уменьшения таких накрытий задач является использование унимодулярных преобразований, с помощью которых исходная задача сводится к некоторой эквивалентной ей задаче ЦП [34].

Во многих прикладных задачах исходные данные не фиксированы, а изменяются в некотором интервале. В связи с этим актуальна проблема исследования задач с такими данными и поиск методов их решения, -учитывающих специфику задачи [50,51]. В [32] на примере дискретной задачи планирования производства с интервальными данными продемонстрирован подход к решению подобных задач, построена модификация алгоритма перебора L - классов. В данной работе продолжены исследования в рассматриваемом направлении, построенные алгоритмы использованы для решения задачи планирования производства с интервальными данными.

Следует отметить, что дискретная задача планирования производства и ее варианты широко используются для моделирования большого числа практических задач, таких как выбор проектов, распределение капитала [95], расположение предметов в системах сборки по заказу [74] и других. Указанные задачи являются NP-трудными [94], поэтому актуальным'является построение алгоритмов их приближенного решения [89,100].

Цель диссертации — разработка, теоретическое и экспериментальное исследование алгоритмов целочисленного линейного программирования с использованием L - разбиения:

Для достижения поставленной цели решались следующие задачи:

1. Построить семейства задач целочисленного линейного программирования для исследования алгоритмов, основанных на использовании релаксационных множеств задач.

2. Получить оценки числа итераций для алгоритмов отсечения, ветвей и границ, перебора L - классов на базе предложенных семейств. Найти унимодулярные преобразования, упрощающие структуру задач и повышающие эффективность алгоритмов.

3. Исследовать устойчивость первого алгоритма Гомори при малых изменениях релаксационного множества задачи ЦЛП. Предложить унимодулярные преобразования, улучшающие поведение алгоритма.

4. Разработать алгоритмы перебора L - классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках.

5. Создать программное обеспечение, провести экспериментальные исследования рассматриваемых алгоритмов.

Методы исследования Обоснованность и достоверность научных положений, результатов и выводов, содержащихся в диссертационной работе, основывается на фундаментальных положениях математического моделирования, дискретной оптимизации, целочисленного линейного программирования, применении компьютерных технологий и подтверждаются результатами численного эксперимента.

Научная новизна работы состоит в следующем.

1. Построены и исследованы семейства задач ЦЛП для анализа алгоритмов отсечения, метода ветвей и границ .и перебора L - классов и других, основанных на использовании релаксационных множеств задач.

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

3. На основе одного из построенных семейств задач доказана неустойчивость первого алгоритма Гомори по релаксационному множеству.

4. Разработаны и апробированы алгоритмы перебора L - классов для решения дискретной задачи планирования производства с интервальными данными.

Практическая ценность. Предложенные алгоритмы перебора L - классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках применимы в случае задач достаточно большой размерности. Полученные результаты используются при тестировании алгоритмов, в научных исследованиях и учебном процессе. Результаты работы нашли применение в лаборатории дискретной оптимизации ОФ ИМ СО РАН при исследовании алгоритмов отсечения и перебора L - классов, в частности, при изучении вопросов их устойчивости. Кроме того, полученные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики ОмГУ им. Ф. М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.

Апробация работы. Результаты диссертации докладывались на XXIX Региональной научной студенческой конференции ОмГУ «Молодежь третьего тысячелетия» (Омск, 2005), III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006), XIII Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2007), IV Всероссийской научной молодежной конференции «Под знаком Сигма> (Омск, 2007), Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 2007), VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 2007), XIV Байкальской международной школе-семинаре (Иркутск-Северобайкальск, 2008), а также на научных семинарах в Омском филиале Института математики им. C.JI. Соболева СО РАН, Омском государственном университете им. Ф. М. Достоевского (2005-2010) и Институте вычислительной математики и математической геофизики СО РАН.

Публикации. Основные результаты диссертации опубликованы в 10 научных работах [9-14,37,42,43,78], три из них - в изданиях из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (101 наименование). Объем диссертации - 112 страниц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Колосов, Антон Павлович

Основные результаты работы заключаются в следующем:

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

2. Доказано, что первый алгоритм Гомори не является устойчивым при малых изменениях релаксационного множества задачи ЦЛП. Найдены унимодулярные преобразования пространства, улучшающие поведение алгоритма на построенных семействах задач.

3. Разработаны алгоритмы перебора L — классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках. Приведены унимодулярные преобразования, ускоряющие процесс перебора L - классов.

4. Создано программное обеспечение, в котором реализованы рассматриваемые алгоритмы, проведены экспериментальные исследования, в том числе на тестовых задачах из известной электронной библиотеки OR-Library, показавшие перспективность предложенных алгоритмов.

Заключение

В диссертации проведено исследование ряда известных алгоритмов целочисленного линейного программирования с использованием /^разбиения и унимодулярных преобразований пространства. Предложены и реализованы новые алгоритмы для решения дискретной задачи планирования производства с интервальными данными, выполнены экспериментальные исследования.

Список литературы диссертационного исследования кандидат физико-математических наук Колосов, Антон Павлович, 2010 год

1. Аделыпин А.В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения //Автоматика и телемеханика. - 2004. - т. - С. 35 -42.

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

3. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука. Сиб. отд-е, 1978. - 160 с.

4. Береснев B.JI. Дискретные задачи размещения и полиномы от булевых переменных. Изд-во Ин-та математики, Новосибирск, 2005. - 408 с.

5. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. - 333 с.

6. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

8. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика. 2004. - №3. - С. 48 - 54.

9. Девятерикова М.В., Колоколов А.А., Колосов А.П. Исследование некоторых алгоритмов целочисленного программирования с использованием /^разбиения и унимодулярных преобразований: Препринт. Омск: ОмГУ, 2009. - 20 с.

10. Девятерикова М.В., Колоколов А.А., Колосов А.П. Об одном подходе к решению дискретной задачи планирования производства с интервальными данными // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14. Ш. С. 48-57.

11. Девятерикова М.В., Колоколов А.А., Колосов А.П. Решение задачи о рюкзаке с интервальными данными на основе перебора L-классов // Материалы третьей международной конференции «Танаевские чтения» , Минск, 2007. С. 51-55

12. Девятерикова М.В., Колоколов А.А., Колосов А.П. Упимодулярные преобразования для задач целочисленного программирования и анализ эффективности их применения //Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16. №2, С. 48-62.

13. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Изд-во НГУ, Новосибирск, 1996. - 167 с.

14. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

15. Емеличев В.А., Подкопаев Д.П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2, Институт математики им. С.Л.Соболева СО РАН, 2001, т. 8. С. 47-69.

16. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций Сер. 2, 2000. т.7. -С. 22-46.

17. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрГУ - Центр "Фактория Пресс 2000. - 303 с.

18. Забиняко Г.И. Пакет программ целочисленного линейного программирования //Дискретный анализ и исследование операций. 1999. Т.6.- № 2. С. 32 - 41.

19. Заблоцкая О. А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации //Дискретная оптимизация и численные методы решения прикладных задач. Новосибирск: ВЦ СО АН СССР, 1986. - С. 21 - 27.

20. Забудскин Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. 1990. - Вып. 30. -С. 35 - 45.

21. Заикина Г. М. Колоколов А. А. Левапова Т. В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 25-41.

22. Касселс Дж.В.С. Введение в геометрию чисел. Издательство «Мир» . М.: 1965. 421 с.

23. Ковалев М. М. Дискретная оптимизация (целочисленное программирование). Изд. 2-е, стереотипное. М.: Едиториал УРСС, 2003. — 192 с.

24. Колоколов А. А. Методы дискретной оптимизации. Учебное пособие. Омск: ОмГУ, 1984. -76 с.

25. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исследования операций. 1994. № 2.- С. 18-39.

26. Колоколов А.А. Регулярные разбиения в целочисленном программировании //Методы решения и анализа задач дискретной оптимизации.- Омск: ОмГУ, 1992. С. 67 - 93.

27. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора ^классов //Прикладная математика и информационные технологии. Омск, 2005. - С. 68 - 79.

28. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задачи выполнимости с использованием метода перебора ^классов // Информационные технологии. — 2009. — №2. С. 54-59.

29. Колоколов А.А., Девятерикова М.В. Алгоритмы перебора /^классов для задачи о рюкзаке с интервальными данными. Препринт. Омск: Изд-во ОмГУ, 2001. 20 с.

30. Колоколов А.А., Девятерикова М.В. Анализ устойчивости /^разбиения множеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т.7. - №2. -С. 47 - 53.

31. Колоколов А.А., Девятерикова М.В. Задачи целочисленного программирования и унимодулярные преобразования // Труды XIV Байкальской международной школы-семинара. Иркутск, 2008. — Т.1. -С. 111 - 118.

32. Колоколов А.А., Девятерикова М.В., Заозерская JI.A. Регулярные разбиения в целочисленном программировании: Учебное пособие. Омск: ОмГУ. - 2007. - 48 с.

33. Колоколов А.А., Заозерская JI.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Труды XIV Байкальской международной школы-семинара. Иркутск, 2008. -Т.1. - С. 388 - 395.

34. Колоколов А.А., Колосов А.П. Анализ некоторых алгоритмов целочисленного программирования с использованием /^разбиения // Информационный бюллетень Ассоциации математического программирования. № 11. УрО РАН. Екатеринбург, 2007. - С. 186.

35. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора /^классов для решения некоторых задач размещения //Вестник Омского университета. Омск: ОмГУ, 1996. - №1. - С. 21 - 23.

36. Колоколов А.А., Нагорная З.Е., Гуселетова О.Н., Ярош А.В. Математические модели и программный комплекс для проектирования эскизов одежды //Прикладная математика и информационные технологии. Омск, 2005. - С. 80 - 98.

37. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Параллельный алгоритм перебора i^-классов для задачи выполнимости //Материалы III Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 2006. С. 102.

38. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости: Препринт. Омск: ОмГУ, 2006 - 19 с.

39. Колосов А.П. О некоторых алгоритмах приближенного решения задачи о рюкзаке // Материалы VI Международной научно-технической конференции «Динамика систем, механизмов и машин» , Омск, ноябрь 2007. с. 49 - 53.

40. Колосов А.П. Оценки числа итераций для некоторых алгоритмов целочисленного программирования // Тезисы IV Всероссийской научной молодежной конференции «Под знаком Сигма» , май 2007, на электронном носителе. С. 244.

41. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации //Изв. АН СССР. Техн. кибернетика. 1988.- т. С. 65 - 77.

42. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969. 368 с.

43. Косарев Н.А., Рубанова Н.А. Об отсечениях Бендерса для некоторых задач размещения предприятий // Материалы Российской конф. «Дискретный анализ и исследование операций» . Новосибирск, 2004.- С. 164.

44. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и приложения. -М. 2001. - С. 84 - 117.

45. Кузнецова А.А., Стрекаловский А.С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации //ЖВМ и МФ. -1999. Т.39. - М. - С. 9 - 16.

46. Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т.1, т. С. 38 - 48.

47. Левин В. И. Дискретная оптимизация в условиях интервальной неопределенности // Автоматика и телемеханика. 1992. N2 7. С. 97 - 106.

48. Левин В. И. Булево линейное программирование с интервальными коэффициентами // Автоматика и телемеханика. 1994. №7. С. 111 - 122.

49. Леонтьев В.К. Устойчивость в линейных дискретных задачах // Про-бл. кибернетики. М.: Наука, 1979. - Вып. 35. - С. 169 - 184.

50. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 248 с.

51. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика. 2004. - № 2. - С. 43 - 54.

52. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука., 1990. - 488 с.

53. Мухачева Э.А., Мухачева А.С. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. - № 2. - С. 101 - 112.

54. Панюков А.В. Квазицелочисленность релаксационного многогранника задачи Вебера // Тр. XI межд. Байкальской школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - С. 171 - 174.

55. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

56. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

57. Попков В.К. Гиперсетн и структурные модели сложных систем // Системное Моделированне-6, Новосибирск. 1981. - С. 26-48.

58. Попков В.К. Математические модели связности // 2-е изд., испр. и доп. Новосибирск: Изд. ИВМиМГ СО РАН. - 2006. - 490 с.

59. Попов Л.Д. Об одноэтапном методе решения лексикографических вариационных неравенств //Известия вузов. Математика. 1998. - №12 (439). - С. 71 - 81.

60. Привалова Ю.И. Некоторые эвристические алгоритмы для задачи о покрытии множества. Препринт. ОмГУ, Омск, 2007. - 17 с.

61. Сайко Л.А. Исследование мощности L-накрытий некоторых задач о покрытии //Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. - С. 76 - 97.

62. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. К.: Наук, думка, 1995. 170 с.

63. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 472 с.

64. Сигал И.Х., Иванова А.П. Введение в прикладное и дискретное программирование: модули и вычислительные алгоритмы. М.: Физмат-лит, 2002. - 240 с.

65. Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации //Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. - Вып. 30. - С. 61 - 71.

66. Страуструп Б. Язык программирования С++. Специальное издание. М.: Бином. - 2001. - 1099 с.

67. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. М.: Мир, 1991. - 702 с.

68. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. - 520 с.

69. Червак Ю.Ю., Червак О.Ю. Один из способов формулирования па-рето-лексикографических задач оптимизации // Кибернетика и системный анализ, 1996, №1. С. 108-110.

70. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. - 190 с.

71. Akcay Y., Xu S. Н. Joint inventory replenishment and component allocation optimization in an assemble-to-order system // Management Science. 2004. No. 50. P. 99 - 116.

72. Benders J. F., van Nunen J. A. E. E. A property of assignment type mixed integer linear programming problems // Operations Research Letters, Volume 2, Issue 2, June 1983. P. 47-52

73. Chvatal V., Cook W., Iiartmann M. On cutting-plane proofs in combinatorial optimization // Linear Algebra and its Applications, Volumes 114-115, March-April 1989. P. 455-499

74. Devyaterikova M.V., Kolokolov A. A. L-class enumeration algorithms for some interval production planning problem // Proc. 12th IFAC Symposium on Information Control Problems in Manufacturing INCOM'2006. St. Etienne, 2006. V. 3. P. 9 - 13.

75. Devyaterikova M.V., Kolokolov A.A., Kolosov A.P. L-class enumeration algorithms for one discrete production planning problem with interval input data // Computers and Operations Research, Volume 36, Issue 2, February 2009. C. 316 - 324.

76. Edmonds J.R., Pulleyblank W.R. Facets of 1-matching polyhedra // C. Berge, D.R. Chuadhuri (Eds.), Hypergraph Seminar, Springer-Verlag, Heidelberg, 1974. P. 214-242.

77. Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture- Notes in Computer Science, 2000. Vol. 1829. - P. 84 - 95.

78. Eremeev A.V., Kolokolov A.A. On some genetic and Zr-class enumeration algorithms in integer programming //Proc. of the First Intertational Conference on Evolutionary Computation and its Applicatios. Moscow, 1996. - P. 297 - 303.

79. Glover F., Laguna M. Tabu Search. University of Colorado at Boulder Hardbound, July 1997. 408 p.

80. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. - 432 p.

81. Gomory R.E. Outline of an algorithm for integer solutions to linear programs // Bulletin of the American Mathematical Society 64 (1958). P. 275-278.

82. Hooker J.N. Generalized resolution and cutting planes //Annals of Operations Research. 1988. - V.12. - P. 217 - 239.

83. Jeroslow R. Cutting-plane theory: Algebraic methods // Discrete Mathematics, Volume 23, Issue 2, 1978. P. 121-150

84. Jeroslow R. Cutting-Plane Theory: Disjunctive Methods // Annals of Discrete Mathematics, Volume 1, 1977. P. 293-330

85. Jeroslow R. An Introduction to the Theory of Cutting-Planes // Annals of Discrete Mathematics, Volume 5, 1979. P. 71-95

86. Johnson D. Approximation algorithms for combinatorial problems //Journal of Comput. System Science. 1974. - V.9. - P. 256 - 278.

87. Kolokolov A. A., Dcvyaterikova M. V. Stability analysis of some discrete optimization algorithms. DOM'2004, Proceedings, Omsk 2004. P. 180 - 184.

88. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On hybrid L-class enumeration and genetic algorithm for set covering problem //15th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. - P. 117.

89. Kouvelis P., Yu G. Robust discrete optimization and its applications. Dordrecht: Kluwer Academic Publishers. 1997. 356 p.

90. Land A.H., Doig A.G. An Automatic Method for Solving Discrete Programming Problems. Econometrica, 28 (1960), P. 497-520.

91. Lin E. Y.-H. A bibliographical survey on some well-known non-standard knapsack problems // INFOR 36(4). 1998. P. 274-317.

92. Lu L. L., Chiu S. Y., Cox L. A. Optimal project selection: Stochastic knapsack with finite time horizon // Operations Research. 1999. No. 50. P. 645-650.

93. Manjoub A., Mihelic J., Rapine C., Robic B. k-center problem with uncertainty: flexible approach // Proc. of Discrete Optimization Methods in Production and Logistics (DOM-2004). Omsk, 2004. P. 75-80.

94. Martello S., Toth P. Knapsack problems : algorithms and computer implementations. John Wiley and Sons. 1990. 296 p.

95. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. A Wiley-Interscience Publication: John Wiley and Sons, inc., 1999. 784 p.

96. Reeves C. Genetic Algorithms for the Operation Researcher // INFORMS -Journal on Computing. 1997. - Vol.9, №3. - P. 231 - 250.

97. Vazirani Vijey V. Approximation Algorithms // Springer, 2002. 380 p.101. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html