Введение 6
1 Основные понятия 31
1.1 Задачи комбинаторной оптимизации . . . . . . . . . . . . . . . . . . . . . . . 31
1.2 Сложность задач и алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.1 Анализ алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.2 Классы сложности задач . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3 Элементы теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.4 Выпуклые многогранники . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.5 Линейное программирование и многогранник задачи . . . . . . . . . . . . . . 54
1.6 Число фасет . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.7 Размер коэффициентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
1.8 Сложность расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.9 Целочисленное программирование . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.9.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.9.2 Релаксация линейного программирования . . . . . . . . . . . . . . . . 70
1.9.3 Модели целочисленного программирования . . . . . . . . . . . . . . . 71
1.10 Аппроксимационные алгоритмы и разрыв целочисленности . . . . . . . . . . 73
1.11 Полиэдральные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.11.1 Смежность вершин и симплекс-подобные алгоритмы . . . . . . . . . . 80
1.11.2 Диаметр графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
1.11.3 Кликовое число и конусные разбиения пространства . . . . . . . . . . 89
2 Релаксационные многогранники 98
2.1 Релаксации разрезного и булева квадратичного многогранников . . . . . . . 99
2.1.1 Многогранник задачи о разрезе . . . . . . . . . . . . . . . . . . . . . . 99
2.1.2 Булев квадратичный многогранник и ковариантное отображение . . . 100
2.1.3 Канонический вид и блочная матрица . . . . . . . . . . . . . . . . . . 102
2.1.4 Некоторые свойства релаксационного многогранника BQPLP (n) . . . 103
2.1.5 Ориентированный максимальный разрез . . . . . . . . . . . . . . . . . 105
2.1.6 Минорные характеристики матрицы
корневого полуметрического многогранника . . . . . . . . . . . . . . . 106
2
2.1.7 Метрический многогранник и графические вершины . . . . . . . . . . 110
2.1.8 Алгоритм генерации графических
вершин метрического многогранника . . . . . . . . . . . . . . . . . . . 115
2.1.9 Знаменатели дробных вершин метрического
многогранника и гипотеза Поляка-Туза . . . . . . . . . . . . . . . . . 118
2.1.10 Задача распознавания целочисленности . . . . . . . . . . . . . . . . . 126
2.1.11 Распознавание целочисленности
на метрическом многограннике BQPLP (n, 3) . . . . . . . . . . . . . . . 128
2.1.12 Неинвертируемые гиперграфы . . . . . . . . . . . . . . . . . . . . . . . 132
2.1.13 Гиперграфы точек метрического многогранника . . . . . . . . . . . . 136
2.1.14 Последовательность релаксаций BQPLP (n, k) . . . . . . . . . . . . . . 140
2.1.15 Релаксация BQPLP (n, 4) . . . . . . . . . . . . . . . . . . . . . . . . . . 141
2.1.16 Релаксация BQPLP (n, 5) . . . . . . . . . . . . . . . . . . . . . . . . . . 146
2.1.17 Релаксация BQPLP (n, 6) . . . . . . . . . . . . . . . . . . . . . . . . . . 150
2.1.18 Трёхмерная структура координат метрического многогранника . . . . 152
2.2 Многогранник задачи 3-выполнимость . . . . . . . . . . . . . . . . . . . . . . 159
2.2.1 Определение многогранника . . . . . . . . . . . . . . . . . . . . . . . . 159
2.2.2 Постановка задач о 3-выполнимости специального вида
в форме распознавание целочисленности . . . . . . . . . . . . . . . . . 160
2.2.3 Нецелочисленные вершины . . . . . . . . . . . . . . . . . . . . . . . . 167
2.2.4 Задача целочисленного программирования на SATPLP (m, n) . . . . . 176
2.2.5 Полиномиально разрешимые подзадачи распознавания
целочисленности на SATPLP (m, n) . . . . . . . . . . . . . . . . . . . . . 189
2.2.6 Задача о 2-3 раскраске двудольного графа
с ограничениями по рёбрам . . . . . . . . . . . . . . . . . . . . . . . . . 197
2.3 Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
2.3.1 Булев квадратичный многогранник . . . . . . . . . . . . . . . . . . . . 200
2.3.2 Многогранник задачи 3-выполнимость . . . . . . . . . . . . . . . . . . 201
3 Полиэдральные графы 202
3.1 Задача о разрезе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
3.1.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
3.1.2 Многогранник и конусные разбиения для задачи о разрезе . . . . . . 207
3.1.3 Критерии смежности в графах
конусных разбиений задачи о разрезе . . . . . . . . . . . . . . . . . . . 209
3.1.4 Кликовое число . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.1.5 Диаметр графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
3.1.6 Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
3.1.7 Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
3.2 Точки на сфере с центром в начале координат . . . . . . . . . . . . . . . . . . 223
3.3 Остовные деревья с ограничением на число листьев и диаметр . . . . . . . . 224
3
3.3.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
3.3.2 Многогранник задачи об остовном дереве . . . . . . . . . . . . . . . . 226
3.3.3 Остовное дерево с ограничением на число висячих вершин . . . . . . 227
3.3.4 Остовное дерево ограниченной степени . . . . . . . . . . . . . . . . . . 230
3.3.5 Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
3.4 Сбалансированный и несбалансированный двудольный подграфы . . . . . . 232
3.4.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
3.4.2 Сбалансированный полный двудольный подграф . . . . . . . . . . . . 235
3.4.3 Максимальный полный двудольный подграф . . . . . . . . . . . . . . 239
3.4.4 Минимальный полный двудольный подграф . . . . . . . . . . . . . . . 240
3.4.5 Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
3.5 Многогранник задачи 3-выполнимость . . . . . . . . . . . . . . . . . . . . . . 244
3.5.1 Смежность вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
3.5.2 Диаметр и кликовое число . . . . . . . . . . . . . . . . . . . . . . . . . 246
3.5.3 Свойство Трубина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
3.5.4 Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
3.6 Пирамидальные циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
3.6.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
3.6.2 Многогранник пирамидальных циклов . . . . . . . . . . . . . . . . . . 251
3.6.3 Граф многогранника пирамидальных циклов . . . . . . . . . . . . . . 252
3.6.4 Диаметр и кликовое число графа
многогранника пирамидальных циклов . . . . . . . . . . . . . . . . . . 258
3.7 Пирамидальные туры с шагами назад . . . . . . . . . . . . . . . . . . . . . . 261
3.7.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
3.7.2 Пирамидальные туры с шагами назад . . . . . . . . . . . . . . . . . . 262
3.7.3 Вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . . . 264
3.7.4 Необходимое и достаточное условие смежности . . . . . . . . . . . . . 266
3.7.5 Алгоритм проверки смежности . . . . . . . . . . . . . . . . . . . . . . 279
3.7.6 Диаметр графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
3.7.7 Кликовое число . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
3.7.8 Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
3.8 Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
4 Гамильтоново разложение 4-регулярного мультиграфа 288
4.1 Многогранник коммивояжёра . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
4.2 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
4.3 Модели целочисленного линейного программирования . . . . . . . . . . . . . 293
4.3.1 Модель Данцига-Фалкерсона-Джонсона . . . . . . . . . . . . . . . . . 293
4.3.2 Модель Миллера-Такера-Землина . . . . . . . . . . . . . . . . . . . . . 294
4.3.3 Другие модели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
4.4 Поиск с возвратом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
4
4.4.1 Алгоритм поиска с возвратом на основе построения простого пути . . 297
4.4.2 Алгоритм поиска с возвратом
на основе цепного фиксирования рёбер . . . . . . . . . . . . . . . . . . 299
4.5 Алгоритм имитации отжига . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
4.5.1 Общая схема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
4.5.2 Множество допустимых решений . . . . . . . . . . . . . . . . . . . . . 304
4.5.3 Функции энергии и план охлаждения . . . . . . . . . . . . . . . . . . . 307
4.5.4 Построение соседнего решения . . . . . . . . . . . . . . . . . . . . . . . 308
4.6 Поиск с чередующимися окрестностями . . . . . . . . . . . . . . . . . . . . . 308
4.6.1 Множество допустимых решений . . . . . . . . . . . . . . . . . . . . . 309
4.6.2 Целевая функция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
4.6.3 Цепное фиксирование рёбер . . . . . . . . . . . . . . . . . . . . . . . . 309
4.6.4 Локальный поиск для ориентированных графов . . . . . . . . . . . . . 310
4.6.5 Спуск с чередующимися окрестностями
для неориентированных графов . . . . . . . . . . . . . . . . . . . . . . 311
4.6.6 Итоговый алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
4.7 Вычислительные эксперименты . . . . . . . . . . . . . . . . . . . . . . . . . . 316
4.8 Итоги главы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Заключение 329
Список литературы 331
Статьи в изданиях, рекомендованных ВАК . . . . . . . . . . . . . . . . . . . . . . 350
Свидетельства о регистрации программ для ЭВМ . . . . . . . . . . . . . . . . . . 352
Другие публикации автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
