Конспект: точные методы на практике

Понятия

Наибольшее независимое множество - наибольший набор вершин без рёбер между ними.

Основа экспоненты - x в оценке xⁿ; для ветвления - корень уравнения, повторяющего его форму.

Целочисленная программа - линейная цель и ограничения, часть переменных целые (обычно 0/1). ЛП-релаксация - она же без требования целости; её оптимум - граница.

Отсекающая плоскость - неравенство, верное для всех целых решений и нарушенное дробной точкой.

Распространение единиц - скобка, где все литералы ложны, кроме одного свободного, делает его истинным. DPLL - перебор с возвратом плюс распространение. CDCL - DPLL плюс обучение на конфликтах и прыжки назад.

Что унести

СНАЧАЛА ПОСЧИТАЙ n
посильное n = ln(бюджет) / ln(основа);  бюджет 10⁹:
    2ⁿ - 29     1,618ⁿ - 43     1,4656ⁿ - 54
независимое множество: ветвиться по вершине наибольшей степени,
    при степени <= 1 брать без ветвления:  T(n) <= T(n−1) + T(n−3)
    24 вершины: 590 вызовов против 16,8 млн подмножеств
отдельные части решать отдельно: время складывается
    три пятиугольника: 2661 вызов целиком, 63 по частям

ЦЕЛОЧИСЛЕННАЯ ПРОГРАММА - ШАБЛОНЫ
если D, то A                   x_D <= x_A
не больше одного из B, C       x_B + x_C <= 1
хотя бы один из E, F           x_E + x_F >= 1
только открытый склад          x_ij <= y_i         (сильно)
                               Σ_j x_ij <= n·y_i   (слабо)
z = x_A · x_B                  z <= x_A, z <= x_B, z >= x_A + x_B − 1
склады: граница слабой 49, сильной 61, оптимум 61
проекты: релаксация 29,5 (x_B = 0,5), оптимум 28 (A, B, F)

ВЕТВИ И ОТСЕЧЕНИЯ
узел: решить релаксацию
    несовместна / граница не лучше рекорда  → закрыть
    целая                                   → рекорд
    дробная x_k                             → x_k = 1 и x_k = 0
проекты: 13 узлов вместо 64 наборов
отсечение нечётного цикла из k вершин: Σ x >= (k + 1) / 2
    пятиугольник: 2,5 → 3
остановлен по времени: оптимум между рекордом и границей

SAT
DPLL: распространить единицы → тупик? → выбрать переменную → две ветки
    невыполнимая формула из 8 переменных: 129 вызовов → 11
раскраска в 3 цвета: на вершину 4 скобки, на ребро 3
    Петерсен: 85 скобок, 7 вызовов;  K4: 34 скобки, невыполнима
CDCL: конфликт → по причинам до одного литерала текущего уровня
      → выученная скобка → прыжок на наибольший из остальных уровней
не больше одного из k:  парами k(k−1)/2,  счётчиком 3k − 4
    k = 100: 4950 против 296
трудные случайные 3-SAT: около 4,27 скобки на переменную

Ловушки джокера

Отказался от точного ответа на тридцати объектах. NP-трудность - про рост, а не про запрет.

Ветвился по первой попавшейся вершине. Посильный размер падает почти вдвое.

Не разделил вход на части. Произведение вместо суммы.

Взял «большое M» с запасом. Релаксация ничего не стоит, решатель путается в округлениях.

Округлил дробный ответ релаксации. Бюджет лопается или оптимум теряется; решатель ветвится.

Прочитал ответ остановленного решателя как оптимум. Это рекорд с разрывом до границы.

Забыл скобки «хотя бы один цвет». Вершину можно не красить вовсе - раскраска «найдётся» у любого графа.

Закодировал «не больше одного из тысячи» парами. Полмиллиона скобок.

Ждал от CDCL чудес на принципе Дирихле. Резолюции там нужна экспонента.

Проверь себя

Откуда в ветвлении для независимого множества основа 1,4656 и сколько вершин она позволяет? Почему отдельные части графа решают отдельно? Запиши «если - то», «не больше одного», «хотя бы один» и произведение двух переменных. Чем сильная запись лучше слабой? Когда решатель закрывает узел и что такое отсекающая плоскость? Как распространение единиц находит тупики раньше перебора? Разбери конфликт из урока: какая скобка выучена и куда прыжок? Сколько скобок у счётчика для k = 50?

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