Исследование устойчивости задач и алгоритмов целочисленного программирования на основе регулярных разбиений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.

Глава 1. Вопросы устойчивости в дискретной оптимизации.

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

1.2 Основные результаты по устойчивости задач дискретной оптимизации

1.3 Метод регулярных разбиений.

1.4 L-структура задач целочисленного программирования и ее свойства

Глава 2. Исследование устойчивости задач целочисленного программирования на основе L-разбиения

2.1 Анализ общей задачи целочисленного программирования

2.2 Оценки для целочисленного выпуклого программирования

2.3 Задачи булева программирования

2.4 Некоторые специальные задачи

Глава 3. Разработка и исследование алгоритмов перебора

L-классов

3.1 Задачи с интервальными данными.

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

3.3 Алгоритмы перебора L-классов для задач ЦП с интервальными данными.

3.4 Приближенные алгоритмы.

3.5 Результаты вычислительного эксперимента

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

К задачам целочисленного программирования сводятся многие задачи, возникающие в экономике, управлении, планировании и других областях [45, 55, 57, 61, 68, 71]. Условие целочисленности позволяет учесть такие факторы как неделимость объектов, наличие альтернатив, дискретность процессов и т.д.

В настоящее время в целочисленном программировании развиваются такие направления как исследование структуры и сложности решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы. Этим вопросам посвящены многие статьи и монографии [2-6, 20, 23, 26-28, 39, 40, 45-47, 55-57, 61, 62, 68, 69, 71, 82, 93, 94].

Значительная часть методов решения задач ЦП основана на использовании релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации. Релаксационное множество задачи ЦП определяется системой ограничений, получающейся из исходной путем исключения условия целочисленности. В процессе решения задачи оно последовательно изменяется с помощью вводимых дополнительных линейных ограничений до получения оптимального решения или другого требуемого результата.

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

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

Исследования устойчивости в дискретной оптимизации охватывают широкий круг вопросов, в том числе:

- определение и изучение областей устойчивости [31, 72-74];

- получение необходимых и достаточных условий устойчивости [1, 8, 30, 32, 36, 37, 54, 63, 84];

- вычисление и оценки радиусов устойчивости [3, 7, 20, 49, 50-54, 66, 67];

- построение алгоритмов нахождения радиуса устойчивости, оценки их сложности [2-6, 83];

- возможность покрытия любого шара в пространстве исходных данных шарами устойчивости [67];

- регуляризация неустойчивых задач [22, 38];

- параметрический анализ и разработка алгоритмов для задач с интервальными данными [34, 58, 59, 62, 64, 78, 88, 89].

В связи с указанной проблематикой представляют интерес исследования вопросов устойчивости в области непрерывной оптимизации, например, [25, 48, 62].

Во многих работах, посвягценых устойчивости задач дискретной оптимизации, рассматривается устойчивость задач целочисленного линейного программирования [54, 56, 70, 72, 74, 77, 92], а также устойчивость траекторных задач [1-7, 49-53, 83]. Значительная часть работ посвящена устойчивости многокритериальных (векторных) задач целочисленного программирования [8, 17-21, 30, 32, 36-38, 63, 84]. Вместе с тем ряд важных вопросов до последнего времени был недостаточно изучен. Один из них - устойчивость релаксационных множеств, в том числе дробных накрытий задач ЦП.

В диссертации развивается новый подход к исследованию устойчивости задач целочисленного программирования, основанный на методе регулярных разбиений. Указанный метод был предложен А.А. Колоко-ловым для исследования свойств задач ЦП, построения и анализа алгоритмов, связанных с релаксацией условия целочисленности. С использованием этого подхода исследуется сложность решения задач, изучается структура релаксационных множеств, вводятся и исследуются новые классы отсечений, строятся оценки числа итераций для ряда известных алгоритмов решения задач целочисленного программирования, разрабатываются новые алгоритмы [26, 27, 39, 40, 44, 65, 82, 87]. Значительное число результатов получено на основе L-разбиения, в частности, предложен метод перебора L-классов для решения задач целочисленного программирования. В последнее время найдены новые возможности применения метода регулярных разбиений - исследование вопросов устойчивости [9, 11-14, 41, 42, 79, 80, 85, 86]. Этот метод позволяет получить результаты не только об устойчивости решений и структуры задач ЦП, но и об устойчивости некоторых алгоритмов при изменении исходных данных.

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

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

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

Диссертация состоит из введения, трех глав и заключения.

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

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

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

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

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

Заключение

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

1. Буслаева JI.T. Об устойчивости приближенных решений задач маршрутной оптимизации / / Алгоритмы и программные средства параллельных вычислений. 1999. - N 3. - С. 16-33.

2. Гордеев Э.П. Полиномиальные алгоритмы вычисления радиуса устойчивости для двух классов задач выбора // Докл. АН СССР. 1987. - Т. 297, N 5. - С. 1040-1043.

3. Гордеев Э.Н. Алгоритмический и постоптимальный анализ устойчивости решений задач дискретной оптимизации: Дис. . д-ра физ.-мат. наук. М.: ВЦ АН СССР - 1992. - 247 с.

4. Гордеев Э.Н. Об устойчивости задач на узкие места // ЖВМ и МФ. 1993. - Т. 33, N 9. - С. 1391-1402.

5. Гордеев Э.Н., Леонтьев В.К. Траекторные параметрические задачи // ЖВМ и МФ. 1984. - Т. 24, N 1. - С. 37-46.

6. Гордеев Э.Н., Леонтьев В.К. Об оценках сложности табулирования траекторных задач // ЖВМ и МФ. 1985. - Т. 25, N 8.1. С. 1272-1275.

7. Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // ЖВМ и МФ. 1996. - Т. 36, N 1. - С. 66-72.

8. Гороховик В.В., Рачковский Н.Н. Об устойчивости задач векторной оптимизации // Вестник АН БССР. Серия физ.-мат. наук. -1990. N 2. - С. 3-8.

9. Девятерикова М.В. Об устойчивости L-накрытий задач булева программирования // Международная конференция "Дискретный анализ и исследование операций": Тезисы докладов. Новосибирск,2000. С. 145.

10. Девятерикова М.В. Решение задачи о рюкзаке с интервальными данными на основе метода перебора L-классов // Научная молодежная конференция "Молодые ученые на рубеже третьего тысячелетия": Материалы конференции. Омск, 2001. - С. 67-69.

11. Девятерикова М.В. Анализ устойчивости L-структуры задач булева программирования // Вестник Омского университета. Омск,2001. N 1. - С. 15-17.

12. Девятерикова М.В., Колоколов А.А. Об устойчивости дробных накрытий задач целочисленного программирования// Международная конференция "Проблемы оптимизации и экономические приложения": Тезисы докладов. Омск, 1997. - С. 59-61.

13. Девятерикова М.В., Колоколов А.А. Об устойчивости L-структуры задач целочисленного программирования // Международная конференция " Дискретный анализ и исследование операций": Тезисы докладов. Новосибирск, 1998. - С. 63.

14. Девятерикова М.В., Колоколов А.А. Устойчивость L-структуры задач целочисленного выпуклого программирования // Вестник Омского университета. Омск, 2000. - N 1. - С. 21-23.

15. Девятерикова М.В., Колоколов А.А. Об одном алгоритме перебора L-классов для задачи о рюкзаке с интервальными данными // Всероссийская конференция " Алгоритмический анализ неустойчивых задач": Тезисы докладов. Екатеринбург, 2001. - С. 207.

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

17. Емеличев В.А., Кравцов М.К., Подкопаев Д.П. О радиусе квазиустойчивости многокритериальной траекторной задачи // Доклады АН Беларуси. 1996. - Т. 40, N 1. - С. 9-12.

18. Емеличев В.А., Кричко В.Н. О радиусе устойчивости паретовско-го оптимума векторной задачи булева программирования // Известия Академии наук республики Молдова. 1999. - N 1. - С. 79-84.

19. Емеличев В.А., Никулин Ю.В. Условия сильной квазиустойчивости векторной линейной траекторной задачи // Доклады АН Беларуси. Сер. физ.-мат. наук. - 2000. - N 2. - С. 38-41.

20. Емеличев В.А., Перепелица В.А. Сложность линейных многокритериальных задач // Дискретная математика. 1994. - Т. 6., вып. 1. - С. 3-33.

21. Емеличев В.А., Подкопаев Д.П. О количественной мере устойчивости векторной задачи целочисленного программирования // ЖВМ и МФ. 1998. - Т. 38, N 11. - С. 1801-1805.

22. Емеличев В.А., Янушкевич О.А. О регуляризации многокритериальной задачи целочисленного линейного программирования // Известия вузов. Математика. 1999. - N 1. - С. 38-42.

23. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. 2000. - Сер. 2. Т. 7. N 1. - С. 47-60.

24. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. - 248 с.

25. Еремин И.И. Общая теория устойчивости в линейном программировании // Известия вузов. Математика. 1999. - N 12. - С. 43-52.

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

27. Заозерская JI.A. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. - 16 с.

28. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции // Дискретный анализ и исследование операций. 1998. - Сер. 1. Т. 5. N 4. - С. 45-60.

29. Карась В.М. Устойчивость решений комбинаторных оптимизационных задач // Автоматика и вычислительная техника. 1987. -N 2. - С. 42-50.

30. Клепикова М.Г. Об устойчивости линейной задачи многокритериальной оптимизации // ЖВМ и МФ. 1987. - Т. 27, N 2.1. С. 178-188.

31. Козерацкая JI.H. Области устойчивости одной задачи целочисленного программирования // Докл. АН УССР. Сер. А. - 1985.1. N 2. С. 57-60.

32. Козерацкая Л.Н. Задачи векторной оптимизации: устойчивость в пространстве решений и в пространстве альтернатив // Кибернетика и системный анализ. 1994. - N 6. - С. 122-133.

33. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Вопросы устойчивости, параметрический и постоптимальный анализ задач дискретной оптимизации // Кибернетика. 1983. - N 4 - С. 83-92.

34. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Исследование задач дискретной оптимизации // Кибернетика и системный анализ. 1993. - N 3. - С. 78-93.

35. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко И.В. Задачи дискретной оптимизации: исследование устойчивости // Обозрение прикладной и промышленной математики. 1995. - N 1.

36. Козерацкая Л.И., Лебедева Т.Т., Сергиенко Т.В. Необходимые и достаточные условия устойчивости многокритериальных задач целочисленного программирования // Докл. АН УССР. Сер. А. -1988. N 19. - С. 76-78.

37. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.В. Задача частично-целочисленной векторной оптимизации: вопросы устойчивости // Кибернетика. 1991. - N 1. - С. 58-61.

38. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.В. О регуляризации задач целочисленной векторной оптимизации // Кибернетика.1993. N 3. - С. 172-176.

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

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

41. Колоколов А.А., Девятерикова М.В. Регулярные разбиения и устойчивость задач целочисленного программирования // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН, 1999. - N 8. - С. 161-162.

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

43. Колоколов А.А., Заозерская JI.A. Регулярные разбиения и лексикография: Учебно-методическое пособие. Омск: ОмГУ, 1999. -31 с.

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

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

46. Кочетов Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации // Международная конференция "Дискретный анализ и исследование операций": Материалы конференции. Новосибирск, 1998. - С. 21-24.

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

48. Левин В.И. Задачи нелинейной оптимизации с интервальными параметрами // Информационные технологии. 2000. - N 1.1. С. 15-19.

49. Леонтьев В.К. Устойчивость задачи коммивояжера // ЖВМ и МФ. 1975. - Т. 15, N 5. - С. 1293-1309.

50. Леонтьев В.К. Устойчивость в комбинаторных задачах выбора // Докл. АН СССР. 1976. - Т. 228, N 1. - С. 23-25.

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

52. Леонтьев В.К. Устойчивость решений в линейных экстремальных задачах: Дис. . д-ра физ.-мат. наук. М.: ВЦ АН СССР, 1981. -228 с.

53. Леонтьев В.К., Гордеев Э.Н. Качественное исследование траектор-ных задач // Кибернетика. 1986. - N 5. - С. 82-89, 105.

54. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программирования // ЖВМ и МФ. 1988.

55. Т. 28, N 10. С. 1475-1481.

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

57. Математическая оптимизация: вопросы разрешимости и устойчивости // Под ред Е.Г. Белоусова, Б. Банка. М.: МГУ, 1986. -216 с.

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

59. Рощин В.А., Семенова Н.В., Сергиенко И.В. Вопросы решения и исследования одного класса задач неточного целочисленного программирования // Кибернетика. 1989. - N 2. - С. 42-47.

60. Рощин В.А., Семенова Н.В., Сергиенко И.В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными // ЖВМ и МФ. 1990. - Т. 30, N 5. -С. 786-791.

61. Семенова Н.В. Решение одной задачи обобщенного целочисленного программирования // Кибернетика. 1984. - N 5. - С. 25-31.

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

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

64. Сергиенко Т.И. Об устойчивости по ограничениям многокритериальной задачи целочисленного программирования // Докл. АН УССР. Сер. А. 1989. - N 3. - С. 79-81.

65. Сергиенко И.В., Семенова Н.В. Задачи целочисленного программирования с неоднозначно заданными данными: точные и приближенные решения // Кибернетика и системный анализ. 1995.1. N 6. С. 75-86.

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

67. Сотсков Ю.Н. Радиус устойчивости е-приближенного решения булевой задачи минимизации линейной формы // Препринт N 21. -Минск: Институт техн. кибернетики АН Белоруси, 1991. 28 с.

68. Сотсков Ю.Н. Исследование устойчивости приближенного решения булевой задачи минимизации линейной формы // ЖВМ и МФ. 1993. - Т. 33, N 5. - С. 785-795.

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

70. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. - 328 с.

71. Швартин С.М. Исследование устойчивости транспортных задач // ЖВМ и МФ. 1978. - Т. 18, N 1. - С. 235-240.

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

73. Bank В. Stability analysis in pure and mixed integer linear programming // Lecture notes in control and inf. sci. 1980.1. N 23. P. 148-153.

74. Bank В., Hansel R. Stability of mixed-integer quadratic programming problems // Math. Progr. Study. 1984. - N 21.

75. Bank В., Mandel R. Quantitative stability of (mixed) integer linear optimization // Lect. Notes Econ. Math. Syst. 1988. - N 304, P. 3-15.

76. Blair С. E., Jeroslow R.G. The value function of an integer program: II // Discr. Math. 1979. - Vol. 25, N 1. - P. 28-47.

77. Blair C.E., Jeroslow R.G. Computational complexity of some problems in parametric discrete programming. I // Math. Oper. res. 1986. -N 11, P. 241-250.

78. Cook W., Gerards A.M.H., Schrijver A., Tardos E. Sensitivity theorems in integer linear programming // Math. Progr. 1986. -Vol. 34, N 3. - P. 251-264.

79. Cooper A.W. Postoptimality analysis in nonlinear integer programming the right-hand side case // Nav. Res. Log. Quart. 1981.-Vol. 28, N 2. - P. 301-307.

80. Devyaterikova M.V., Kolokolov A.A. On L-structure stability of integer convex programming problems // International Conference on Operations Research: Abstracts. Dresden, 2000. - P. 37.

81. Devyaterikova M.V., Kolokolov A.A. Analysis of L-structure stability of convex integer programming problems // Operations Research Proceedings, Springer, 2000. P. 49-54.

82. Devyaterikova M.V., Kolokolov A.A. L-class enumeration algorithms for knapsack problem with interval data // International Conference on Operations Research: Book of Abstracts. Duisburg, 2001. - P. 118.

83. Eremeev A.V., Kolokolov A.A. On Some Genetic and L-class Enumeration Algorithms in Integer Programming // Proc. of the First International Conference on Evolutionary Computation and Its Applications. Moscow, 1996. - P. 297-303.

84. Gordeev E., Leontev V. Polynomial algorithms for stability analysis // International Conference on Operations Research: Abstracts. -Dresden, 2000. P. 36.

85. Iacob P. The solution of the pareto optimization problems in decision space and in the objective space, stability properties // Proc. Colloq. Approximation and Optimization Clui-Napoca. - 1984. - P. 254-259.

86. Kolokolov A.A., Devyaterikova M.V. On stability of L-structure of integer programming problems // International Conference on Operations Research: Abstracts. Zurich, 1998. - P. 52-53.

87. Kolokolov A.A., Devyaterikova M.V. Analysis of L-structure stability of a knapsack problem // International Conference " Combinatorial Optimization 2000": Abstracts. England, Greenwich, 2000. - P. 8.

88. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On Hybrid L-class Enumeration and Genetic Algorithm for Set Covering Problem // 15-th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. - P. 117.

89. Libura M. Integer programming problems with inexact objective function // Contr. and Cybern. 1980. - Vol. 9, N 4. - P. 189-202.

90. Non-linear parametric optimization / B. Bank, J. Guddat. J. Klatte at all. // Berlin: Akad.-Verlag. 1982. - 226 p.

91. Seelander J. Einige Bemerkungen zur Bestimmung von Stabilitatsbereichen in der reinganzzahligen linearen Optimierung // Math. Operationsforsch. und Statist., Ser. Optimiz. 1980. - 11, N 2.- S. 261-271.

92. Sensivity, stability and parametric analysis // Math, program, study.- 1984. Vol. 21, N 1-6. - P. 1-242.

93. Sturmfels В., Thomas R.R. Variation of cost functions in integer programming // Math. Prog. 1997. - Vol. 77, N 3. - P. 357-387.

94. Vazirani V.V. Approximation algorithms. Springer. - 2001. - 378 p.

95. Zhang L.S., Gao F., Zhu W.X. Nonlinear integer programming and global optimization //J. Comput. Math. 1999. - Vol. 17, N 2.1. P. 179-190.