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

• Корбут, Мария Федоровна
• кандидат физико-математических наук
• 2013

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

Оглавление

Введение

Глава 1. Математические модели и методы для задач об упаковке множества

1.1. Постановки задач и приложения

1.2. Задача о наибольшем независимом множестве

1.3. Полиномиально разрешимые случаи

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

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

Глава 2. Исследование задач об упаковке множества с системами ограничений блочной структуры

2.1. Проектирование одной системы радиосвязи

2.2. Анализ ¿-накрытий задач со связующими столбцами

2.3. Оценки мощности ¿-накрытий для некоторых семейств задач

2.4. Подклассы ^тР-трудных задач

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

3.1. Исследование процесса перебора ¿-классов

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

3.3. Алгоритмы решения задач блочной структуры

3.4. О приближенном решении задач

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

4.1. Описание разработанного комплекса программ

4.2. О среднем числе итераций метода перебора L-классов

4.3. Исследование алгоритмов для задач об упаковке множества

4.4. Решение задач об упаковке множества, блочной структуры

Заключение

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

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

Введение

Актуальность темы. Исследование различных задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП) [9.20,29.74.81,90.92]. Особый интерес к задачам ЦП вызван тем. что во многих случаях необходимо находить оптимальные решения, удовлетворяющие условию целочисленности. Указанные задачи имеют большое теоретическое и практическое значение.

Модели и методы целочисленного программирования [8,21.25,27.3739,69.78,85,91,93] применяются для анализа и решения задач дискретной оптимизации [4,39,64.67.73,85], например, оптимального размещения [57. 11. 32. 33. 52. 53, 77], о покрытии [26. 84]. максимальной выполнимости логической формулы [2, 3, 43, 44], о рюкзаке [49, 56, 129, 133], задач проектирования с логическими ограничениями [14. 54, 63]. оптимизации на графах [79.80], поэтому данной проблематике посвящено значительное число публикаций.

Задачи об упаковке множества занимают важное место в дискретной оптимизации и имеют широкий круг приложений в экономике, планировании, управлении, теории информации и других областях [24.68,96-98.121.131,140.142]. Для указанных задач изучается их структура и сложность, выделяются полиномиально разрешимые случаи и семейства трудных задач, устанавливаются новые свойства многогранников, разрабатываются и исследуются алгоритмы точного и приближенного решения [66, 96, 100, 106, 107. 111. 114, 116, 124, 132, 138].

Многие результаты получены с применением целочисленного линейного программирования и отражены в работах [34,47.71,115,134.136.137]. В связи с этим исследование задач об упаковке множества и разработка алгоритмов их решения является актуальным направлением.

При моделировании сложных экономических и технических систем часто возникают оптимизационные задачи большой размерности, которые относятся к задачам целочисленного программирования блочного типа [1, 94]. При этом блоки обычно представляют в моделях отдельные объекты, подразделения фирмы, части одного устройства, различные временные отрезки и т.п. Они могут быть соединены между собой ограничениями, в которых выражена необходимость использования общих ресурсов, обеспечения взаимосвязи решений для всего предприятия, технологического процесса или периода планирования. Некоторые постановки предстваляют собой задачи об упаковке множества блочной структуры. Перспективным направлением анализа и решения таких задач является применение декомпозиционных методов, в которых учитывается блочная структура модели. Так. в работе [94] исследуются дискретные задачи квазиблочного типа, в [72, 99] предлагаются различные методы приведения систем ограничений задач ЦП к блочному виду, в [76] строится алгоритм для решения задачи прямоугольной упаковки на базе использования блочных структур.

Для решения задач об упаковке множества можно применять алгоритмы, разработанные на основе известных методов целочисленного программирования, в частности схемы ветвей и границ [130. 138], различных процедур неявного перебора допустимых решений (см., например, [95]). метода лексикографической оптимизации [28], алгоритмов отсечений [10,31,40,87,88,118,135]. Среди процедур приближенного решения рассматриваемых задач наиболее известны генетические алгоритмы, методы локальной оптимизации, алгоритмы муравьиных колоний, схемы жадного типа [106,107,111,114] и другие.

Для иследоваиия задач целочисленного программирования, построения

и анализа алгоритмов их решения A.A. Колоколовым был предложен метод регулярных разбиений [40—42. 47]. получивший применение и развитие во многих работах. В соответствии с этим подходом релаксационное множество задачи ЦП разбивается определенным образом на классы эквивалентности. Наиболее изученным является одно из таких разбиений - L-разбиепие, элементы которого называются L-классами. На его основе построены алгоритмы перебора L-классов, используемые для решения различных задач ЦП [3,43-45,47].

С помощью регулярных разбиений изучена структура и сложность ряда задач ЦП. разработаны и исследованы новые алгоритмы и классы правильных отсечений, построены оценки числа итераций для известных алгоритмов целочисленного линейного программирования, выполнены исследования устойчивости некоторых задач и процессов их решения, проведена серия вычислительных экспериментов [16-18,26,30,35,42,47.49, 55,84]. Значительное число результатов получено на основе L-разбиения [2, 3,19,35,42-45.47.50,51,57-С1,65.82.83,109.110.127].

В последнее время рассматриваются вопросы применения метода регулярных разбиений в сочетании с унимодулярными преобразованиями [46.89]. которые позволяют улучшить структуру задач и повысить эффективность алгоритмов их решения [18,129]. Выполнен анализ z-алгоритма решения задач ЦЛП [12], в частности исследована его регулярность относительно кубических и других разбиений [55].

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

построить оценки в среднем числа итераций ряда алгоритмов при решении задачи об упаковке множества и задачи о рюкзаке [34-30,49.70]. Поэтому представляется перспективным дальнейшее развитие и применение данного подхода для исследования задач об упаковке множества.

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

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

1) исследовать математические модели ряда проблем, возникающих при проектировании сложных систем, в частности систем связи с использованием задач об упаковке множества:

2) провести анализ структуры и сложности задач об упаковке множества, включая постановки блочного типа на основе Ь-разбиения, выделить и изучить семейства задач с Ь-накрытиями экспоненциальной мощности:

3) построить и исследовать алгоритмы, основанные на переборе ¿-классов и лексикографической оптимизации для решения рассматриваемых задач:

4) разработать научно-исследовательский вариант комплекса программ для задач об упаковке множества, в том числе с учетом ограничений блочного вида;

5) выполнить экспериментальные исследования предложенных алгоритмов.

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях: XXXIII научно-практической студенческой конференции «Молодежь III тысячелетия», (г. Омск. 2009), IV. V Всероссийских конференциях «Проблемы оптимизации и экономические приложения», (г. Омск, 2009, 2012), VII Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск. 2009), Российской конференции «Дискретная оптимизация и исследование операций», (Республика Алтай, 2010),

XIV Всероссийской конференции «Математическое программирование и приложения», (г. Екатеринбург. 2011). XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения», (г. Иркутск, 2011). Международной конференции «Optimization and Applications ОРТ1МА-2011». (г. Петровац, Черногория. 2011). Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова (г. Екатеринбург, 2012), па заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (Новосибирск, 2013). а также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» Омского филиала ФГБУН Института математики им. С.Л. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009-2013).

Публикации. Основные результаты диссертации опубликованы в 11 научных работах [50.51.57-61.65.82,83,128]. три из них - в журналах из списка ВАК [50,51,57].

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

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

Вторая глава посвящена исследованию задач об упаковке множества с системами ограничений блочной структуры на основе L-разбиения.

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

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

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

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

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

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

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

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

2. Разработаны гибридные алгоритмы, основанные на переборе Ь-классов и методе лексикографической оптимизации для решения задач об упаковке множества в общей постановке и блочной структуры.

3. Построены нижние оценки числа итераций алгоритмов перебора Ь-классов при решении рассматриваемых задач.

4. Создан научно-исследовательский вариант комплекса программ, включающий реализацию разработанных в диссертации алгоритмов.

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Корбут, Мария Федоровна, 2013 год

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

[1] Авербах И.Л., Цурков В.И. Целочисленные оптимизационные модели блочного типа // Математическое моделирование. - 1990. - Т. 2, № 2. -С. 39-57.

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

[3] Адельшин A.B., Кучин А.К. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Омский научный вестник. - 2011. - № 1. - С. 5-9.

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

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

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

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

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

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

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

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

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

[13] Гмурман В.Е. Теория вероятностей и математическая статистика. Учебное пособие. - М.: Высшее образование, 2006. - 479 с.

[14] Гуселетова О.Н., Колоколов A.A. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика. - 2008. - № 10. -С. 176-182.

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

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

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

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

[19] Девятерикова М.В., Колоколов A.A., Косарев H.A. Анализ устойчивости по целевой функции некоторых алгоритмов целочисленного программирования // Известия вузов. Математика. -2011. - № 4. - С. 23-32.

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

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

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

[23] Емеличев В.А., Кузьмин К.Г. Анализ чувствительности эффективного решения векторной булевой задачи минимизации проекций линейных функций на R+ и // Дискретный анализ и исследование операций. Серия 2. - 2001. - Т. 12. - С. 24-43.

[24] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990. - 384 с.

[25] Емеличев В.А., Подкопаев Д.П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2. - 2001. - Т. 8. -С. 47-69.

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

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

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

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

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

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

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

[33] Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискретный анализ и исследование операций. - 2011. - Т. 18, К5 4. — С. 49-65.

[34] Заозерская Л.А., Колоколов A.A. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества //

Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2008. - Т. 1. - С. 388-395.

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

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

[37] Картак В.М. Метод группировки для решения непрерывной задачи линейного раскроя // Дискретный анализ и исследование операций. -2009. - Т. 3, № 16. - С. 47-62.

[38] Картак В.М., Месягутов М.А., Мухачева Э.А., Филиппова A.C. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. - 2009. - № 6. - С. 167-180.

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

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

[41] Колоколов A.A. Применение регулярных разбиений в целочисленном программировании // Известия вузов. Математика. - 1993. - № 12. -С. 11-30.

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

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

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

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

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

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

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

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

[50] Колоколов A.A., Корбут М.Ф. Исследование одного класса задач об упаковке множества // Вестник Омского университета. - 2012. - № 4. -С. 21-26.

[51] Колоколов A.A., Корбут М.Ф. Решение задачи об упаковке множества с ограничениями блочной структуры // Омский научный вестник. -2013. - № 1(117). - С. 29-33.

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

[53] Колоколов A.A., Леванова Т.В., Федоренко A.C. Исследование декомпозиционного подхода для двухстадийной задачи размещения // Вестник Омского университета. - 2010. - № 4(58). - С. 24-31.

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

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

[56] Колоколов A.A., Орловская Т.Г. О некоторых унимодулярных преобразованиях для задачи о рюкзаке // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2011. - Т. 4. - С. 161-166.

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

[58] Колоколов A.A., Рыбалка М.Ф. Разработка и анализ алгоритмов решения задачи об упаковке множества с использованием L-разбиения / / Труды Всероссийской конференции «Проблемы

оптимизации и экономические приложения». - Омск: Полиграфический центр КАН, 2009. - С. 138.

[59] Колоколов A.A., Рыбалка М.Ф. Исследование и решение задачи об упаковке множества блочной структуры // Материалы VII Международной научно-технической конференции «Динамика систем, механизмов и машин». - Омск: ОмГТУ, 2009. - Кн. 3. - С. 55-59.

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

[61] Колоколов A.A., Рыбалка М.Ф. Анализ алгоритмов перебора L-классов для решения задачи об упаковке множества // XIV Всероссийская конференция «Математическое программирование и приложения»: Информационный бюллетень № 12. - Екатеринбург, 2011. - С. 187.

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

[63] Колоколов A.A., Ярош A.B. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. - 2010. -Т. 90, № 2. - С. 234-238.

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

[65] Корбут М.Ф. Решение задач об упаковке множества с использованием последовательной оптимизации и перебора L-классов. Препринт. -Омск: Ом ГУ, 2013. - 24 с.

[66] Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975. - 480 с.

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

[68] Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.

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

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

[71] Кузюрин H.H., Фомин С.А. Эффективные алгоритмы и сложность вычислений. Учебное пособие. - М.: МФТИ, 2007. - 312 с.

[72] Лемтюжникова Д.В., Свириденко A.B., Щербина O.A. Алгоритм выделения блочно-древовидной структуры в разреженных задачах дискретной оптимизации // Таврический Вестник Информатики и Математики. - 2012. - № 1(20). - С. 44-55.

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

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

[75] Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. - М.: Наука, 1983. - 208 с.

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

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

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

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

[80] Попков Г.В., Попков В.К., Величко В.В. Математические основы моделирования сетей связи. Учебное пособие. - Москва: Горячая линия-Телеком, 2012. - 183 с.

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

[82] Рыбалка М.Ф. Решение некоторых задач об упаковке множества // Труды научно - практической студенческой конференции «Молодежь III тысячелетия». - Омск, 2009. - С. 260-261.

[83] Рыбалка М.Ф. Анализ некоторых алгоритмов для задачи об упаковке множества с матрицей блочной структуры // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2011. - Т. 4. - С. 197-202.

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

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

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

[87] Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации // Управляемые системы. - 1990. -Вып. 30. - С. 61-71.

[88] Симанчёв Р.Ю. Выпуклые многогранники и фасетные неравенства. Учебно-методическое пособие. - Омск: Изд-во ОмГУ, 1999. - 40 с.

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

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

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

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

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

[94] Щербина O.A. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // ЖВМ и МФ. -1986. - Т. 26, № 9. - С. 1339-1349.

[95] Balas Е. An Additive Algorithm for Solving Linear Programs with Zero -One Variables // Operations Research. -1965. - vol. 3, № 4. -P. 517-546.

[96] Borndörfer R. Aspects of Set Packing, Partitioning, and Covering. PhD thesis, Technische Universität Berlin, 1998.

[97] Borndörfer R., Schlechte Т. Models for railway track allocation // Technical Report 07-02, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 2007a.

[98] Borndörfer R., Schlechte Т. Models for railway track allocation // Technical Report 07-02, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 2007b.

[99] Borndörfer R., Ferreira C.E., Martin A. Decomposing matrices into blocks // SI AM Journal on Optimization. - 1998. - № 9. - P. 236-269.

[100] Bron C., Kerbosh J. Algorithm 457 - Finding all cliques of an undirected graph // Communications of the ACM. - 1973. - № 16. - P. 575-577.

[101] Caprara M., Fischetti M., Toth P. Modeling and solving the train timetabling problem // Operations Research. - 2002. - № 50(5). -P. 851-861.

[102] Chudnovsky M., Cornuejols G., Liu X., Seymour P., Vuskovic K., Cleaning for Bergeness // Technical report, Princeton University, 2003.

[103] Chudnovsky M., Seymour P. Recognizing Berge graphs // Technical report, Princeton University, 2003.

[104] Cornuejols G., Liu X., Vuskovic K. A polynomial algorithm for recognizing perfect graphs // Technical report, Carnegie Mellon University, 2003.

[105] Cramton P., Shoam Y., Steinberg R. Combinatorial Auctions // The MIT press: Cambridge, MA, 2006.

[106] Delorme X., Gandibleux X., Rodriguez J. GRASP for set packing problems // European Journal of Operational Research. - 2004. -№ 153(3). - P. 564-580.

[107] Andrade D.V., Resende M., Werneck R.F. Fast local search for the maximum independent set problem // AT&T Labs Research Technical Report TD-7BBST2, 2008.

[108] Dirac G.A. On regid circuit graphs // Anh. Math. Sem. Univ. Hamburg. -1961. - № 25. - P. 71-76.

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

[110] Eremeev A.V., Kolokolov A.A., Zaozerskaya L.A. A Hybrid Algorithm for Set Covering Problem // Proc. of International Workshop «Discrete Optimization Methods in Scheduling and Computer-Aided Design». -Minsk, 2000. - P. 123-129.

[111] Fisher M., Wolsey L. On the Greedy Heuristic for Covering and Packing Problems // SIAM Journal on Algebraic and Discrete Methods. - 1982. -№ 3. - P. 584-591.

[112] Fulkerson D.R. Blocking and anti-blocking pairs of polyedra // Mathematical Programming. - 1971. - № 1. - P. 168-194.

[113] Fulkerson D.R., Cross O.A. Incidence matrices and interval graphs // Pacific Journal of Mathematics. - 1965. - № 15. - P. 835-855.

[114] Gandibleux X., Delorme X., T'Kindt V. An Ant Colony Optimisation Algorithm for the Set Packing Problem // Ant Colony Optimization

and Swarm Intelligence, Lecture Notes in Computer Sciences. - 2004. -vol. 3172. - P. 49-60.

[115] Garfinkel R., Nemhauser G.L. Integer Programming // John Wiley and Sons, 1972. - P. 302-305.

[116] Gavril F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph // SIAM Journal on Computing. - 1972. - № 1(2). - P. 180-187.

[117] Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs // Journal of Combinatorial Theory (Series B). - 1974. -№ 16. - P. 47-56.

[118] Gomory R.E. Outline of an algorithm for integer solutions to linear programs // Bulletin of the American Mathematical Society. - 1958. -№ 64. - P. 275-278.

[119] Grotschel M., Lovász L., Schrijver A. Polynomial algorithms for perfect graphs // Annals of Discrete Mathematics. - 1984. - № 21. - P. 325-356.

[120] Grotschel M., Lovász L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. - Springer: New York, 1988. - 362 p.

[121] Guo Y., Lim A., Rodrigues B., Zhu Y. Heuristics for a Brokering Set Packing Problem // Proceedings of eighth international symposium on artificial intelligence and mathematics. - 2004. - P. 10-14.

[122] Halldorsson M.M., Radhakrishnan J. Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs / / Algonthmica. - 1997. - Vol. 18. - P. 145-163.

[123] Hoffman K.L., Padberg M. Solving Airline Crew Scheduling Problems by Branch-and-Cut // Management Science. - 1993. - Vol. 39, № 6. -P. 657-682.

[124] Ibarra L. Fully dynamic algorithms for chordal graphs // Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. - 1999. -P. 923-924.

[125] Klein P. Efficient parallel algorithms for chordal graphs // SIAM Journal on Computing. - 1996. - № 25(4). - P. 797-827.

[126] Kolokolov A.A. On the ¿-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.

[127] Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p -median problem //J. Math. Model. Algorithms. -2006. - vol. 5, № 2. - P. 189-199.

[128] Kolokolov A.A., Orlovskaya T.G., Rybalka M.F. Analysis of some integer programming algorithms based on the method of regular partitions // Abstracts of II International conference «Optimization and applications» (OPTIMA-2011). - M.:BU, PAH, 2011. - P. 133-136.

[129] Krishnamoorthy B., Pataki G. Column basis reduction and decomposable knapsack problems // Discrete Optimization. - 2009. - vol. 6, № 3. -P. 242-270.

[130] Land A.H., Doig A.G. An Automatic Method for Solving Discrete Programming Problems // Econometrica. - 1960. - № 28. - P. 497-520.

[131] Lusby R., Larsen J., Ryan D., Ehrgott M. Routing Trains Through Railway Junctions: A New Set Packing Approach // Transportation Science. -2011. - vol. 45, № 2. - P. 228-245.

[132] Maghout K. Applications de e'Algebre de Bool a la Theorie des Graphes // Cahiers du Centre d'Etudes de Recherche Operationnelle de Bruxelles. -1963. - vol. 5. - № 1-2. - P. 21-54.

[133] Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementation. - John Wiley and Sons, 1990. - 308 p.

[134] Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization // Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. - John Wiley and Sons, Inc., New York, 1988. - 763 p.

[135] Padberg M.W. On the facial structure of set packing polyhedra // Mathematical Programming. - 1973. - № 5. - P. 199-215.

[136] Padberg M.W. On the complexity of the set packing polyhedra // Annals of Discrete Mathematics. - 1975. - № 1. - P. 421-434.

[137] Padberg M.W. Covering, Packing and Knapsack Problems // Annals of Discrete Mathematics. - 1979. - № 47. - P. 19-46.

[138] Rebennack S., Oswald M., Theis D.O., Seitz H., Remelt G., Pardalos P.M. A Branch and Cut solver for the maximum stable set problem // Journal of Combinatorial Optimization. - 2011. - Vol. 21, № 4. - P. 434-457.

[139] Rose D.J., Tarjan R.E., Lueker G.S. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. - 1976. - № 5(2). -P. 266-283.

[140] Tajima A., Misono S. Using a set packing formulation to solve airline seat allocation/reallocation problems // Journal of the Operations Research Society of Japan. - 1999. - Vol. 42, № 1. - P. 32-44

[141] Tarjan R.E., Yannakakis M. Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM Journal on Computing. - 1984. - Vol. 13, № 3. - P. 566-576.

[142] Wan P., Jia X., Yao F. Maximum Weighted Independent Set of Links under Physical Interference Model // Wireless Algorithms, Systems, and

Applications. Lecture Notes in Computer Science. - Springer-Verlag, Berlin Heidelberg, 2010. - Vol. 6221. - P. 68-74.

[143] Wilcoxon F. Individual comparisons by ranking methods // Biometrics Bulletin. - 1945. - Vol. 1, № 6. - P. 80-83.

[144] Yildirim E.A., Fan-Orzechowski X. On Extracting Maximum Stable Sets in Perfect Graphs Using Lovdsz's Theta Function // Computational Optimization and Applications. - 2006. - № 33. - P. 229-247.