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

• Заозерская, Лидия Анатольевна
• кандидат физико-математических наук
• 1998

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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ¿-СТРУКТУРЫ ЗАДАЧ О ПОКРЫТИИ

И УПАКОВКЕ МНОЖЕСТВА

1.1. Метод регулярных разбиений и алгоритмы отсечения

1.1.1. Предварительные сведения

1.1.2. Задача о покрытии

1.2. Семейство задач о покрытии Балаша

1.3. Блочно-диагональные задачи о покрытии

1.4. Задача об упаковке

ГЛАВА 2. АЛГОРИТМЫ ПЕРЕБОРА ¿-КЛАССОВ И

ОТСЕЧЕНИЯ

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

о покрытии

2.1.1. Базовый алгоритм

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

2.1.3. Алгоритм перебора ¿-классов с групповым анализом задач

2.1.4. Некоторые свойства алгоритма перебора ¿-классов

и задачи о покрытии

2.2. Прямые алгоритмы отсечения

2.3. Оценки числа итераций и контрпримеры

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

2.4. Об ¿-структуре задач из многопараметрического семейства

2.5. Программное обеспечение и вычислительный эксперимент

2.5.1. Результаты эксперимента для алгоритма перебора

L-классов

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

алгоритмов отсечения

ГЛАВА 3. РЕГУЛЯРНЫЕ СИСТЕМЫ НЕРАВЕНСТВ

3.1. Индекс регулярного разбиения

3.2. Кубические разбиения и их связь с L-разбиениями

3.3. Классификация кубических разбиений

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

3.4.1. Отсечения 1-го алгоритма Гомори

3.4.2. Вполне регулярные отсечения

3.4.3. Отсечения конечного прямого алгоритма

3.4.4. Отсечения z-алгоритма

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

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

Введение

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

В настоящее время целочисленное программирование представляет собой одно из активно развивающихся направлений дискретной оптимизации. Современная проблематика ЦП охватывает такие вопросы как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы, программное обеспечение, экспериментальные исследования и др. [1,5,7,9,12,17,32,3947,53-55,57,58,60,62,63,68,69,77,78,80,84,92].

Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности более "легких" задач непрерывной оптимизации. К таким методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг [40,46]), декомпозиции (с отсечениями Бендерса [35,75,86]), алгоритмы перебора Ь-классов [32] и некоторые другие. Характерными особенностями этих методов являются использование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.

Метод отсечения, один из общих подходов к решению задач как непрерывной, так и дискретной оптимизации, получил свое развитие в работах многих авторов, в том числе в [2,21,40,59,60,66,77,80-82,85, 94]. Отличительной чертой метода является генерация и использова-

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

Для исследования задач ЦП, построения и анализа алгоритмов их решения, основанных на использовании релаксационных множеств, А.А.Колоколовым был предложен метод регулярных разбиений [27,33], получивший дальнейшее развитие, в частности, в работах [6,1014,18,19,21,24,25,28-32,34,35,38,56,86-88].

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

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

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

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

Диссертация состоит из трех глав. В первой главе изучается ¿-структура задач о покрытии и упаковке множества. Задачи о покрытии имеют широкое практическое применение. Например, они возникают при составлении расписаний экипажей на авиалиниях, в задачах информационного поиска, политического районирования, упрощении булевых выражений [41,74]. Кроме того, другие известные задачи оптимизации могут быть сведены к задаче о покрытии [41].

Э.Балашем предложено и исследовано семейство задач о покрытии [65], которое характеризуется значительной разностью оптимальных значений целевых функций целочисленной задачи и ее линейной релаксации. В этом семействе нами выделены задачи, для которых мощность ¿-накрытий растет экспоненциально с увеличением числа переменных. Число ограничений в них также экспоненциально зависит от числа переменных. Из проведенного нами вычислительного эксперимента следует, что эти задачи являются трудными для 1-го алгоритма Гомори, так как глубина его отсечений при их решении близка к 1. Получе-

но точное выражение мощности ¿-накрытия произвольной задачи из рассматриваемого семейства.

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

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

Вторая глава посвящена построению алгоритмов решения задачи о покрытии и исследованию прямых алгоритмов отсечения в целочисленном линейном программировании (ЦЛП). В литературе описаны точные алгоритмы решения задачи о покрытии, основанные на методе ветвей и границ, отсечениях, субградиентной технике и других подходах [41,67,70,74,79,90], а также различные приближенные алгоритмы и эвристики [8,71,73,76,78,84].

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

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

Далее в этой главе исследуются вопросы конечности и построения оценок числа итераций для прямых алгоритмов отсечения. Анализу указанных алгоритмов посвящены работы [21,60,64,81,83,89,94,95]. Известно, что простые реализации прямых алгоритмов отсечения (например, рудиментарный алгоритм - РИА) не являются конечными. Первые контпримеры для РПА были опубликованы в [91]. Эти задачи, построенные в Я3, не решаются за конечное число шагов при некоторых "плохих" стратегиях решения. А.А.Колоколовым [23] построены одно-параметрическое и двухпараметрическое семейства задач ЦЛП (также в трехмерном случае), при решении которых получается бесконечный процесс для любого из вариантов РПА и других более сложных прямых алгоритмов отсечения с управляющими ограничениями. Отметим, что на плоскости для РПА получена верхняя оценка числа итераций [20] и нижняя экспоненциальная оценка для общего случая [22].

Во второй главе на основе результатов из [23] получены новые более широкие семейства задач ЦЛП, также дающие бесконечный процесс для любого из вариантов РПА и более сложных алгоритмов. С использованием указанных семейств строятся задачи ЦЛП в Л3, которые как угодно долго решаются конечным прямым алгоритмом (КПА). Это также обобщает результаты из [23]. На основе изучения ¿-структуры дробных накрытий строится верхняя оценка числа регулярных отсечений, появляющихся при решении двойственными алгоритмами части задач из построенных семейств. Исследуется структура дробных накрытий этих же задач для кубических разбиений.

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

покрытии.

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

Данный вопрос изучается для кубических разбиений и класса ограниченных сверху множеств [21]. В этом случае получено значение индекса, зависящее от структуры булева вектора, порождающего кубическое разбиение.

Рассматривается регулярность известных классов отсечений (отсечений Гомори [21,40,60,82], вполне регулярных отсечений булева программирования [11] и некоторых других) относительно кубических разбиений. Показана регулярность ¿-алгоритма, предложенного А.А.Вотяковым [3], для специального класса множеств.

Основные результаты диссертации опубликованы в работах [15,16, 34,36,37,48-52] и докладывались на III Всесоюзной школе "Дискретная оптимизация и компьютеры" (Таштагол, 1987), Омской областной математической конференции (1987), 10 Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988), 6 Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989),

III Всесоюзном семинаре "Дискретная математика и ее приложения" (Москва, 1990), 7 Всесоюзной конференции "Математическое программирование и приложения" (Свердловск, 1991), XI международной Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1998), а также на семинарах в Институте математики им. С.Л.Соболева СО РАН, в Омском комплексном отделе ВЦ СО АН СССР, в Институте информационных технологий и прикладной математики СО РАН.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Заозерская, Лидия Анатольевна

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

1. Проведен анализ задач о покрытии и упаковке множества:

- получены нижние оценки и точное значение мощности Ь-накрытий для семейства задач о покрытии, предложенных Э.Балашем;

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

- получены оценки числа итераций при решении этих задач некоторыми алгоритмами отсечения и методом Лэнд и Дойг.

2. Разработаны и исследованы алгоритмы перебора Ь-классов для точного и приближенного решения задач о покрытии множества. Создано программное обеспечение для алгоритмов перебора Ь-классов, проведены экспериментальные исследования.

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Заозерская, Лидия Анатольевна, 1998 год

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

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

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

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

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

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

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

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

[8] Еремеев A.B. Генетический алгоритм для задачи о наименьшем покрытии множества// Междун. Сиб. конф. по исследованию операций: Мат.конф. - Новосибирск: Изд-во ИМ СО РАН, 1998, -С.107.

[9] Еремин И.И. Симметричная двойственность для задач последовательного линейного программирования // ДАН СССР. -1991. -317, N5. -С.1045-1048.

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

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

[12] Забудский Г.Г. Некоторые свойства многогранника задачи о р-медиане// Вестник Омского университета. - Омск: Изд-во ОмГУ, 1996. -N1. - С.1-4.

[13] Заикина Г.М., Колоколов A.A. Экспериментальные исследования в целочисленном программировании с применением L-разбиения// Дискретная оптимизация и анализ сложных систем. - Новосибирск: ВЦ СО АН СССР.- 1989. - С.26-56.

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

[15] Заозерская Л.А. Некоторые гибридные алгоритмы для задачи о покрытии// 10 Всерос. конф."Математическое программирование и приложения", Екатеринбург, февр. 1997: Тез. докл. - Информ. бюлл. АМП N 7. - Екатеринбург, 1997. - С.100.

[16] Заозерская Л.А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества //XI междунар. Байкальская школа-семинар "Методы оптимизации и их приложения", Иркутск, Байкал, 5-12 июля 1998: Труды, том 1 - Иркутск, 1998. -С.139-142.

[17] Исследование операций: пер. с англ. в 2-х т. /Под ред. Дж.Моудера, С.Элмаграби. -М.: Мир. -1981. -Т.1. -712с.; Т.2 -679 с.

[18] Колоколов A.A. Алгоритмы отсечения и некоторые разбиения множеств // Дискретная оптимизация и численные методы решения прикладных задач. - Новосибирск: ВЦ СО АН СССР. -1986. - С.50-67.

[19] Колоколов A.A. Верхняя оценка числа отсечений для первого алгоритма Гомори // Тез. докл. III Всесоюз. конф. по проблемам теоретической киберненики. - Новосибирск, 1974. - С.87-88.

[20] Колоколов A.A. К оценке числа итераций для прямых алгоритмов отсечения в целочисленном линейном программировании // Математический анализ экономических моделей. 4.1. - Новосибирск: ИЭиОПП СО АН СССР, 1971. - С.137-164.

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

[22] Колоколов A.A. Некоторые оценки для прямых алгоритмов отсечения в целочисленном программировании// Математический анализ экономических моделей. Ч.Ш. - Новосибирск: ИЭиОПП СО АН СССР, 1972. - С.154-161.

[23] Колоколов A.A. Некоторые оценки и контпримеры для прямых алгоритмов отсечения// Тез. докл. ГУ Всесоюз. конф. по проблемам теоретической кибернетики. -Новосибирск, 1977. - С.109.

[24] Колоколов A.A. Нижняя оценка числа итераций для одного класса алгоритмов отсечения// Управляемые системы. - Новосибирск: ИМ СО АН СССР, 1983. - Вып. 23. - С.64-69.

[25] Колоколов A.A. Нижняя оценка числа регулярных Р-отсечений для задач целочисленного программирования// Методы мате-

матического программирования и их программное обеспечения. Тез.докл. научн.-техн. конф. - Свердловск, 1984. - С.68.

[26] Колоколов A.A. Об одном прямом алгоритме целочисленного программирования/ / Мат. II конф. молодых экономистов и социологов Сибири и Дальнего Востока. - Новосибирск, 1970. - Вып.III. - С.37-

45.

[27] Колоколов A.A. О лексикографической структуре некоторых выпуклых многогранных множеств// Тез. докл. Y Всесою. конф. по проблемам теоретической кибернетики. - Новосибирск, - 1980. -С.77-79.

[28] Колоколов A.A. О числе отсекающих плоскостей в первом алгоритме Гомори// Проблемы анализа дискретной информации. - Новосибирск: ИЭиОПП СО АН СССР, 1975. - С. 84-96.

[29] Колоколов A.A. О строении некоторых выпуклых многогранных множеств// Методы математического программирования и их программное обеспечения. Тез.докл. научн.-техн. конф. - Свердловск: ИМиМ УрО АН СССР, 1981. - С. 72-73.

[30] Колоколов A.A. О наискорейшем алгоритме в одном классе регулярных процессов отсечения// Методы и программы решения оптимизационных задач на графах и сетях. 4.2. - Тез. докл. III Всесоюзного совещания, Ташкент. - Новосибирск: ВЦ СО АН СССР, -1984. - С.70.

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

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

[33] Колоколов A.A. Регулярные отсечения при решении задач целочисленной оптимизации // Управляемые системы. - Новосибирск: ИМ СО АН СССР, 1981. -Вып. 21. - С.18-25.

[34] Колоколов A.A., Заикина Г.М., Сайко JI.A., Цепкова Е.В. Экспери-

w т и _

ментальный анализ L-накрытии задач целочисленного программирования и алгоритмов отсечения // III Всесоюз. школа "Дискретная оптимизация и компьютеры", Таштагол, 2-9 декабря 1987г.: Тез. докл. - Москва, 1987. - С.117.

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

[36] Колоколов A.A., Сайко Л.А. О некоторых оценочных разбиениях в целочисленном программировании / / Тез. док л 10 Всесоюз. симпозиума "Системы программного обеспечения решения задач оптимального планирования". - М., 1988. - С. 134.

[37] Колоколов A.A., Сайко Л.А. Некоторые лексикографические алгоритмы решения задачи о покрытии// Математическое программирование и приложения (Свердловск, 25 февраля - 1 марта 1991 г.) Тез.докл. - Свердловск.: ИМиМ Ур.отделения АН СССР.-1991.-С.87.

[38] Колоколов A.A., Цепкова Е.В. Верхняя оценка числа регулярных отсечений для одного семейства задач на конусе// Управляемые системы, вып. 25. - Новосибирск. - 1984. - С. 75-79.

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

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

[41] Кристофидес Н. Теория графов. - М.: Мир. - 1978. - 432 с.

[42] Кротов В.Ф., Сергеев С.И. Общий подход к решению задач дискретной оптимизации//Моделирование и оптимизация управляемых динамических систем. -М.: ИПУ СО АН СССР, 1989. -С. 5-11.

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

[44] Лебедев С.С., Шейнман O.K. Двойственность в целочисленном программировании// Экономика и мат. методы. -1981. - N3. -С.593-608.

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

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

[47] Перепелица В.А., Сергиенко И.В. К проблеме нахождения множеств альтернатив в дискретных многокритериальных зада-ча//Кибернетика. -1987. - N5. -С.85-93.

[48] Сайко Л.А. Анализ L-сруктуры некоторых задач о покрытии// Методы и программы решения оптимизационных задач на графах и сетях. Тез. докл. IV Всесоюзного совещания 17-19 окт. 1989г. -Новосибирск: ВЦ СО АН СССР. - 1989, 4.2 - С. 94.

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

[50] Сайко Л.А. О числе итераций прямых алгоритмов отсечения// Дискретная оптимизация и численные методы решения прикладных задач. - Новосибирск: ВЦ СО АН СССР.- 1986. - С. 86-88.

[51] Сайко JI.А. Регулярные системы неравенств для одного класса оценочных разбиений// Методы математического программирования и программного обеспечения. Тез.докл.- Свердловск. ИМиМ Ур.отд. АН СССР.- 1989.-С.185.

[52] Сайко Л.А. Исследование одного класса разбиений в целочисленном программировании// Модели дискретной оптимизации (Управляемые системы).- Новосибирском СО АН СССР, 1989, вып.29.-С.72-82.

[53] Сапоженко A.A., Асратян A.C., Кузюрин H.H. Обзор некоторых результатов по задачам о покрытии// Методы дискретного анализа в решении комбинаторных задач. - Новосибирск, 1977, вып. 30, - С.46-75.

[54] Сервах В.В. Схема динамического программирования для некоторых задач теории расписаний// Международная Сибирская конференция по исследованию операций. Мат. конф. - Новосибирск: Изд-во Института математики СО РАН, 1998, - С.164.

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

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

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

[58] Уздемир А.П., Шмелев В.В. Целочисленные динамические задачи экономического планирования с сетевыми ограничениями. 1,11// Автомат, и телемех. - 1978.-N7. -С.106-115; 1978. -N9. -С.110-120.

[59] Фридман А.А., Вотяков А.А. Регулярные дискретные задачи и метод отсечения// Исследования по дискретной оптимизации. - М.: Наука. - 1976. - С.1-50.

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

[61] Червак Ю.Ю. Об одном методе отсечений для дискретных задач// Укр. мат. журн. -1971. -N.6. - С.839-843.

[62] Шевченко В.Н. Алгебраический подход в целочисленном программировании// Кибернетика. -1984. -4. -С.36-41.

[63] Шлык В.А. О теоретико-групповом подходе в целочисленном линейном программировании //Известия АН СССР. Техническая кибернетика. -1988. -N1.-C.94-105.

[64] Austin Larry M.,Giiandforousii P.. A surrigate cutting plane algorithm for all-integer programming// Comput. and Oper. Res. - 1985. -Vol.12, N3. - P.241-250.

[65] Balas E. A sharp bound on the ration between optimal integer and fractional covers// Math. Oper. Res. - 1984. - Vol.9, N1. - P.l-5.

[66] Balas E. Intersection cuts - a new tupe of cutting planes for integer programming// Math. Oper. Res. - 1971. - Vol.19, N1. - P.19-39.

[67] Balas E. and Ho A. Set coveringe algorithms using cutting planes, heuristics, and subgradient optimization : a computational study// Mathematical Programming Study. - 1980.'- N12.- P.37-60.

[68] Balas E. and Ng S.M. On the set covering politope: I. All then facets with coefficients in {0,1,2}// Mathematical Programming. - 1989. -N 43.- P.57-69.

[69] Balas E. and Ng S.M. On the set covering politope: II. Lifting the

facets with coefficients in {0,1,2}// Mathematical Programming. -1989. - N 45.- P.l-20.

[70] Beasley J.E. An algorithm for set covering problem// Europ. J. Oper. Res. - 1987. - N31.- P.85-93.

[71

[72

[73

[74

[75

[76

[77

[78

Beasley J.E. A Lagrangian heuristic for set-covering problems // Navar Research Logistics. - 1990. - N37,- P.151-164.

Beasley J.E. OR-Library: Distributing test problems by electronic mail // J.Oper. Res. Soc. - 1990. - Vol. 41, N11.- P.1069-1072.

Beasley J.E., Chu P.C. A genetic algorithm for the set covering problem// Europ. J. Oper. Res. - 1995. - N 2. - P.393-404.

Beasley J.E., Jornsten K. Enhancing an algorithm for the set covering problems// Europ. J. Oper. Res. - 1992. - N 58. - P.293-300.

Benders J.F. Partitioning Procedures for Solving of Mixed-variables Programming Problems// Numer. Math. - 1962. - Vol.4, N3. - P.238-252.

Chvatal V. A greedy heuristic for the set-covering probem// Math. Oper. Res. - 1979. - Vol. 4, N 3. - P.233-235.

Chvatal V. Cutting planes in combinatorics// European J. of Combinatorics. - 1985. - N6. - P.217-226.

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

[79] Fisher M. L., Kedia P. Optimal solution of set covering/partitioning problems using dual heuristics// Management science. - 1990. - Vol.36, N 6. - P.674-688.

[80] Garfinkel R.S., Nemhauser G.L. Integer programming. - Wiley, N.Y., 1972, 426p.

[81] Glover F. A new Foundation for a simplified primal integer programming algorithm// Oper. Res. - 1968. - Vol. 16, N 6. - P.727-740.

[82] Gomory R.E. Outline of an Algorithm for Integer Solution to Linear Programs // Bull. Amer. Math. Soc. - 1958. - Vol.64, N5. - P.275-278.

[83] Hanna Michael E.A. Austin Larry M. An advanced strart algorithm for all integer programming// Comput. and Ops Res. - 1985. - Vol.12, N3. - P.301-309.

[84] Hochbaum D.S. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems // Approximation Algorithms for NP-Hard Problems. Ed. by S.D.Hochbaum, PWS Publishing Company, 1995. - P.94-143.

[85] Jeroslow R.G. Cutting-plane theory: algebraic methods// Discrete Math. - 1978. - Vol.23, N2. - P.121-151.

[86] Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems// Triennal Symposium on Transportation Analysis II. Preprints. Vol. 1. - Capri, Italy, 1994. -P.179-183.

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

[88] Kolokolov A.A. Some L-class enumeration algoritms for Integer Programming Problems// Abstracts of 3rd IFIP WG-7.6 Working

Conference on Optimization-Based Computer-Aided Modelling and Design. - Prague, Czech Republic, 1994. - P.98-99.

[89] Links G. and Rubin David S. Finite primal cutting plane algorithns for integr programs// SIAM J. Control and Optimization. - 1979. -Vol.17, N1. - P.47-55.

[90] Mannino R., Sassano A. Solving hard set covering problems// Operations Research Letters. - 1995. - N.18. - P.l-5.

[91] Mathis S.I.Jr. A Coontrexample to the rudimentary primal integer programming algorithm// Operations Reseach. - 1971. - Vol. 19, N 6. - P.1518-1522.

[92] Padberg M.W., Rinaldi G. Facet identification for the simmetric travelling salesmane problem // Math. Program. - 1990. - 47, N2. -P.219-257.

[93] Trauth C.A., Woolsey R.E. Integer linear programming: a study in computational effeciency// Manag. Sci. -1969. -15.- P.481-493.

[94] Young R.D. A primal (all-integer) programming algorithm. - J. Res. National Bureau of Standards. - 1965, 69B, N 3. - p.213-250.

[95] Young R.D. A simplified primal (all-integer) integer programming algorithm. - Operations Reseach. - 1968, vol. 16, N 6. - p.750-782.