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

• Орловская, Татьяна Геннадьевна
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Орловская, Татьяна Геннадьевна

Оглавление

Введение

1 Модели и методы целочисленного программирования

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

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

1.3 О применении унимодулярных преобразований

2 Исследование и решение задач о рюкзаке на основе Ь — разбиения

2.1 Унимодулярные преобразования для задач о рюкзаке

2.2 Анализ Ь - структуры и алгоритмов решения задач о рюкзаке

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

3 Анализ г — алгоритма решения задач целочисленного линейного программирования

3.1 Специальный класс задач целочисленного линейного программирования иг- алгоритм

3.2 Исследование г - алгоритма с использованием регулярных разбиений

3.3 Об оценках числа итераций

Заключение

Литература

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

Введение

Актуальность темы. Для решения многих задач, возникающих в планировании, управлении, проектировании и других областях, применяются модели и методы целочисленного программирования (ЦП), в которых учитываются такие факторы, как неделимость объектов, дискретность процессов, альтернативность выбора. Аппарат ЦП широко используется при исследовании различных классов задач дискретной оптимизации, в частности задач оптимального размещения [3-5,9,24,42,65], о покрытии [18,72], об упаковке [28,53,63], выполнимости логической формулы [1,34,35], задач с логическими и ресурсными ограничениями [43]. Значительный интерес к задачам ЦП обусловлен их MV - трудностью [12].

Проблематика ЦП является достаточно разнообразной и включает исследование структуры и сложности задач, разработку и анализ методов их решения, изучение вопросов устойчивости задач и алгоритмов, многокритериальные постановки и ряд других [1,2,4-8,13,16,17,19-21,31,32,35, 36,39,42,54-57,60,62,66,67,69,70,73-75,77,79-90,92,95,96].

В настоящее время в целочисленном программировании активно развивается предложенный A.A. Колоколовым метод регулярных разбиений [31, 32,52]. Наиболее изученным разбиением является L - разбиение, на основе которого разработаны алгоритмы решения задачи о покрытии, задачи о рюкзаке, задач выполнимости и других [27,31,39]. С помощью этого метода исследована L - структура некоторых задач ЦП [22,31,32,39,64], построены оценки числа итераций для ряда известных алгоритмов [21, 27, 29], введены новые классы отсечений [23,31,32,75], получены результаты по устойчивости задач и алгоритмов дискретной оптимизации [13,36].

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

Одним из таких направлений, показавших свою продуктивность и актуальность, является построение и исследование упимодулярных преобразований [17,30,77], с помощью которых исходная задача сводится к эквивалентной ей задаче ЦП [15,38]. Применение унимодулярпых преобразований сохраняет множество допустимых целочисленных точек, но может сделать структуру задачи более приемлемой для решения.

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

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

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

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

образований, улучшающих L - структуру задач о рюкзаке.

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

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

4. Исследовать 2 - алгоритм Вотякова A.A. для решения задач ЦЛП на основе регулярных разбиений.

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на IV и V Всероссийских конференциях 11 Проблемы оптимизации и экономические прилоэюения" (Омск, 2009 и 2012), VII Международной научно-тех-пической конференции "Динамика систем, механизмов и машин" (Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Алтай, 2010), 8-й и 9-й Международных конференциях "Интеллектуализация обработки информации" (Кипр, 2010 и Черногория, 2012), XIV Всероссийской конференции 11 Математическое программирование и приложения1'1 (Екатеринбург, 2011), XV Байкальской международной школе-семинаре "Методы оптимизации и их прилоэюения" (Иркутск, 2011), Международной конференции " Алгебра и линейная оптимизация", посвященной 100-летию С.П. Черникова (Екатеринбург, 2012),

на заседании научного семинара отдела математического программирования Института математики и механики им. H.H. Красовского УрО РАН (Екатеринбург, 2012), а также на заседаниях научного семинара "Математическое моделирование и дискретная оптимизация" Омского филиала Института математики им. C.J1. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009 - 2012).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [44-52,64,91], две из них — в журналах из списка ВАК [46,52].

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

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

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

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

В заключении сформулированы основные результаты и выводы диссертационной работы.

Автор благодарит научного руководителя д.ф.-м.н., профессора Коло-колова A.A. за проявленное внимание и поддержку при подготовке данной работы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Орловская, Татьяна Геннадьевна

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

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

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

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

4. Исследован я - алгоритм Вотякова A.A., основанный на использовании унимодулярных преобразований, для решения задач ЦЛП, изучено его поведение относительно регулярных разбиений.

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

Заключение

В диссертации выполнено исследование ряда задач и алгоритмов целочисленного линейного программирования на основе регулярных разбиений и унимодулярных преобразований пространства.

Список литературы диссертационного исследования кандидат физико-математических наук Орловская, Татьяна Геннадьевна, 2013 год

Литература

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

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

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

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

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

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

[7] Быкова В.В. FPT-алгоритмы и их классификация на основе эластичности // ПДМ, 2011. № 2. - С. 40-48.

[8] Васильев И.Л. Метод отсечений для многогранника задачи о рюкзаке // Известия РАН. Теория и системы управления. - 2009. № 1. -С. 74-81.

[9] Васильев И.Л., Климентова К.Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискретный анализ и исследование операций. - 2009. Т. 16. № 2. - С. 21-41.

[10] Вотяков A.A. Некоторые вопросы целочисленного программирования // Экономика и математические методы. 1968. Том 4, вып. 4. -С. 611-621.

[11] Вотяков A.A. О задачах, инвариантных относительно z - округления // Экономика и математические методы. 1971. Том 7, вып. 2. - С. 259-264.

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

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

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

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

[16] Евтушенко Ю.Г., Посыпкин М.А. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач // Доклады Академии наук. - Т. 437, № 2. -С. 168-172.

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

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

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

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

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

[22] Заблоцкая O.A. Двойственные процессы отсечения и L - структура некоторых задач целочисленного программирования: Автореф. дис. канд. физ.-мат. наук: 01.01.09. - Новосибирск, 1985.

[23] Заблоцкая O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании // Управляемые системы. - Новосибирск: ИМ СО АН СССР. 1983. - Вып. 23. - С. 55-63.

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

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

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

[27] Заозерская Л.А., Колоколов A.A. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества // Журнал вычислительной математики и математической физики. 2010. - Т. 50, JV» 2. - С. 242-248.

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

[29] Заозерская Л.А., Колоколов A.A., Гофман Н.Г. Оценки числа итераций для алгоритмов решения некоторых задач булева программирования // Дискретный анализ и исследование операций, 2011. -Т. 18, № 3. - С. 50-65.

[30] Касселс Дж.В.С. Введение в геометрию чисел. Издательство "Мир". М.: 1965.-421 с.

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

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

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

[34] Колоколов A.A., Адельшин A.B., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода

перебора L - классов // Прикладная математика и информационные технологии. - Омск, 2005. - С. 68-79.

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

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

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

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

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

[40] Колоколов A.A., Заозерская JI.A. Построение оценок числа итераций алгоритмов целочисленного программирования на основе метода регулярных разбиений // Проблемы оптимизации и экономические приложения: IV Всеросс. конф. Омск: ПЦ КАН, 2009. - С. 62-67.

[41] Колоколов A.A., Заозерская JI.A. Верхние оценки среднего числа итераций для некоторых алгоритмов решения задачи о рюкзаке // Дискретные модели в теории управляющих систем: тр. VIII Междунар. конф. - Москва, 2009. - С. 101-106.

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

[43] Колоколов A.A., Нагорная З.Е., Гуселетова О.Н., Ярош A.B.

Математические модели и программный комплекс для проектирования эскизов одежды // Прикладная математика и информационные технологии. - Омск, 2005. - С. 80-98.

[44] Колоколов A.A., Орловская Т.Г. Исследование 2 - алгоритма для решения некоторых задач целочисленного программирования // Проблемы оптимизации и экономические приложения: материалы IV всероссийской конф. Омск: Полиграфический центр КАН, 2009. - С. 137.

[45] Колоколов A.A., Орловская Т.Г. О регулярности одного алгоритма решения задач целочисленного программирования // Динамика систем, механизмов и машин: материалы VII междунар. науч.-техн. конф. Омск: Изд-во ОмГТУ, 2009. Кн.З. - С. 51-55.

[46] Колоколов A.A., Орловская Т.Г. Исследование одного алгоритма решения задач целочисленного линейного программирования // Тр. Ин-та матем. и мех. 2010. Т. 16, № 3. - С. 140-145.

[47] Колоколов A.A., Орловская Т.Г. Исследование L - структуры задачи о рюкзаке // Дискретная оптимизация и исследование операций: материалы Российской конф. Новосибирск, 2010. - С. 96.

[48] Колоколов A.A., Орловская Т.Г. Методы улучшения L - структуры задачи о рюкзаке // Математическое программирование и приложения: Информационный бюллетень № 12 XIV Всероссийской конф. Екатеринбург, 2011. - С. 186.

[49] Колоколов A.A., Орловская Т.Г. О некоторых унимодулярных преобразованиях для задачи о рюкзаке // Методы оптимизации и их

приложения: тр. XV Байкальской междунар. шк.-сем. Иркутск, 2011. Т. 4. - С. 161-166.

[50] Колоколов A.A., Орловская Т.Г. Анализ алгоритмов решения некоторых задач о рюкзаке на основе L - разбиения // Алгебра и линейная оптимизация: тезисы междунар. конф., посвященной 100-летию С.Н. Черникова. Екатеринбург, 2012. - С. 94-95.

[51] Колоколов A.A., Орловская Т.Г. Исследование некоторых постановок задачи о рюкзаке и алгоритмов их решения с использованием унимодулярпых преобразований и L - разбиения // Интеллектуализация обработки информации: 9-ая междунар. конф. Черногория, г. Будва, 2012 г.: Сборник докладов. -- М.: Торус Пресс, 2012. -С. 286-289.

[52] Колоколов A.A., Орловская Т.Г., Рыбалка М.Ф. Исследование алгоритмов целочисленного программирования с использованием регулярных разбиений и унимодулярных преобразований // Автоматика и телемеханика. № 2, 2012. - С. 178-190.

[53] Колоколов A.A., Рыбалка М.Ф. Анализ и решение одного класса задач об упаковке множества // Дискретная оптимизация и исследование операций: мат. росс. конф. Новосибирск, 2010. - С. 95.

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

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

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

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

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

[59] Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений. - 2008. -http: //discopal.ispras.ru/ги .book-advanced-algorithms.htm.

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

[61] Лотов А.В. Введение в экономико-математическое моделирование. М.: Наука. Главная редакция физико-математической литературы, 1984. - 392 с.

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

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

[64] Орловская Т.Г. Улучшение структуры семейств задач о рюкзаке с использованием унимодулярных преобразований // Алгебра и линейная оптимизация: тезисы междунар. конф., посвященной 100-летию С.Н. Черникова. Екатеринбург, 2012. - С. 122-124.

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

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

[67] Перепелица В.А. Дискретная оптимизация и моделирование в условиях неопределенности данных: монография // В.А. Перепелица, Ф.Б. Тебуева. - М. : Акад. Естествознания, 2007 (Пенза). - 152 с.

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

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

[70] Попов Л.Д. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации // Автомат, и теле-мех., 2007. - Вып. 5. - С. 171-181.

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

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

[73] Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации // АН УССР, Ин-т кибернетики им. В.М. Глушкова. - 2-е изд., доп. и перераб. - Киев : Наук, думка, 1988. - 471 с.

[74] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2007. - 304 с.

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

|76] Страуструп Б. Язык программирования С++. - Изд-во: Бином, Невский Диалект, 2008. - 1104 с.

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

[78] Троелсен Э. Язык программирования 2010 и платформа .NET 4.0. 5-е изд.: пер. с англ. - М.: ООО иИ.Д. Вильяме", 2011. -1392 с.

[79] Хачай М.Ю. Вычислительная сложность комбинаторных задач, индуцированных коллективными процедурами обучения распознаванию образов // Тр. Ин-та матем. и мех. 2010. Т. 16, № 3. - С. 276-284.

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

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

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

[83] 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.

[84] 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.

[85] 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.

[86] 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.

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

[88] Glover F., Laguna M. Tabu Search. University of Colorado at Boulder Hardbound, July 1997. - 408 p.

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

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

[91] Kolokolov A.A., Orlovskaya T.G., Rybalka M.F. Analysis of some integer programming algorithms based on the method of regular partitions // Optimization and applications(OPTIMA-2011): Proceedings of II International Conference, Petrovac, Montenegro, September 25 -October 2, 2011. - P. 133-136.

[92] Kellerer H., Pferschy U., Pisinger D. Knapsack Problems // Springer. - 2004. - 546 p.

[93] Krishnamoorthy B., Pataki G. Column basis reduction and decomposable knapsack problem // Discrete Optimization. August 2009. 6(3). P. 242-270.

[94] Kolokolov A.A. On the L - structure of integer linear programming problems // System Modelling and Optimization: Proceedings of the 16th IFIP conference on the modelling and optimization. Springer Verlag. 1993. P. 756-760.

[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.