MAX-SAT: монетка, релаксация и лучшее из двух

Если ты посчитаешь, с какой вероятностью монетка и округление релаксации выполняют скобку длины k, объяснишь, почему лучшее из двух не хуже 3/4, и умеешь убрать случайность методом условных ожиданий, листай до «Теперь сам».

Как думаешь, какой способ лучше

Восемнадцать требований к конфигурации сервиса, все сразу несовместимы: «включить кеш», «не включать кеш вместе с отладкой», «если сжатие, то HTTP/2»… Нужен набор флагов, выполняющий как можно больше требований. Два простых способа: подбросить монетку на каждый флаг или решить релаксацию и подбросить монетки со смещёнными вероятностями.

Ответь себе до чтения: какой лучше? Требования вида «включить кеш» - скобка из одного литерала - монетка выполняет через раз. Релаксация на таких скобках уверена: если выгодно включить, y = 1. А требования из трёх-четырёх литералов монетка выполняет почти всегда - и тут релаксация бывает хуже. Каждый способ слаб там, где силён другой.

На что это похоже

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

Доказательство 3/4 устроено именно так: для каждой длины скобки хотя бы один способ хорош, и среднее двух уже не меньше трёх четвертей.

Механизм: две вероятности для одной скобки

Монетка (Джонсон, 1974). Скобка из k литералов разных переменных ложна, только если все k литералов ложны: вероятность 2⁻ᵏ. Выполняется с вероятностью 1 − 2⁻ᵏ ≥ 1/2.

Релаксация. Переменная y_i от 0 до 1 вместо значения флага, z_c - выполнена ли скобка c:

максимизировать  Σ z_c
при условиях     z_c <= Σ y_i (по x_i в скобке) + Σ (1 − y_i) (по ¬x_i)
                 0 <= y_i, z_c <= 1

Округление (Гоманс, Уильямсон, 1994). Поставить x_i = 1 с вероятностью y_i. Скобка ложна с вероятностью - произведение вероятностей, что каждый её литерал ложен. Сумма «вероятностей истинности» литералов не меньше z_c, а произведение при фиксированной сумме самое большое, когда множители равны. Отсюда:

P(скобка ложна) <= (1 − z_c / k)ᵏ
P(выполнена)    >= 1 − (1 − z_c / k)ᵏ >= (1 − (1 − 1/k)ᵏ) · z_c

Последний шаг - кривая 1 − (1 − z/k)ᵏ выпукла вверх, поэтому лежит выше хорды от 0 до 1. Множитель 1 − (1 − 1/k)ᵏ убывает с k к 1 − 1/e.

Лучшее из двух. Для каждой скобки среднее двух вероятностей не меньше 3/4 · z_c - это видно из таблицы ниже. Сумма по скобкам - ожидание среднего двух ответов не меньше 3/4 · LP ≥ 3/4 · OPT, а лучший из двух не хуже среднего.

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

Правило

MAX-SAT: монетка выполняет скобку длины k с вероятностью 1 − 2⁻ᵏ, округление релаксации - с вероятностью не меньше (1 − (1 − 1/k)ᵏ) · z_c. Первое хорошо на длинных скобках, второе на коротких; лучший из двух ответов в ожидании не хуже 3/4 · OPT. Случайность убирается методом условных ожиданий.

Разбор: восемнадцать скобок

Формула на восьми переменных, скобки длины 1-3. Релаксацию решает linprog, оптимум - перебор всех 256 наборов, ozhidanie считает ожидаемое число выполненных скобок по вероятностям, uslovnye фиксирует переменные по одной. Программа запускается в обычном Python со scipy.

import itertools
import numpy as np
from scipy.optimize import linprog

formula = [[-8], [3, 1], [-2, 6], [8], [-4, 5], [-7, 8, 1], [3],
           [-3, -6], [-2, -8], [5], [-2], [-5, 6, -4], [-8, -7],
           [-5, -3, -6], [6, -3, 4], [-7], [-6, -8, 2], [-1, 3]]
n = 8
m = len(formula)

def vypolneno(nabor):
    return sum(any((l > 0) == nabor[abs(l) - 1] for l in s)
               for s in formula)

def ozhidanie(p):
    itog = 0
    for s in formula:
        mimo = 1
        for l in s:
            mimo *= 1 - p[l - 1] if l > 0 else p[-l - 1]
        itog += 1 - mimo
    return itog

# релаксация: переменные y_1..y_n, затем z_1..z_m; максимум Σ z
c = np.concatenate([np.zeros(n), -np.ones(m)])
A, b = [], []
for j, s in enumerate(formula):
    stroka = np.zeros(n + m)
    stroka[n + j] = 1
    pravaya = 0
    for l in s:
        if l > 0:
            stroka[l - 1] -= 1
        else:
            stroka[-l - 1] += 1
            pravaya += 1
    A.append(stroka)
    b.append(pravaya)
lp = linprog(c, A_ub=np.array(A), b_ub=b, bounds=(0, 1))
y = [float(v) for v in lp.x[:n]]

def uslovnye(p):
    p = list(p)
    for i in range(n):
        p[i] = 1
        da = ozhidanie(p)
        p[i] = 0
        if da > ozhidanie(p):
            p[i] = 1
    return [v == 1 for v in p]

opt = max(vypolneno(a) for a in itertools.product([False, True],
                                                  repeat=n))
print(opt, round(-lp.fun, 2), [round(v, 2) for v in y])
print(round(ozhidanie([0.5] * n), 2), round(ozhidanie(y), 2))
print(vypolneno(uslovnye([0.5] * n)), vypolneno(uslovnye(y)))

16 16.67 [0.33, 0.0, 0.67, 0.33, 1.0, 0.33, 0.0, 0.0]
12.62 15.37
16 16

Оптимум 16 из 18 (все 18 сразу нельзя: есть и x₈, и ¬x₈; 17 исключил перебор). Релаксация 16,67 - её дробные y в трети показывают, где формула спорит сама с собой.

Монетка в ожидании выполняет 12,625 скобки (напечатано округлённым до 12,62) - много коротких скобок, и каждая одиночная выполняется лишь через раз. Округление релаксации - 15,37: на коротких скобках оно уверено. А после метода условных ожиданий оба старта дали 16 - ровно оптимум. Ожидание - это гарантия «не хуже», а фиксация переменных по одной часто находит и лучше.

Разбор: почему именно три четверти

Таблица по длине скобки: вероятность монетки, множитель округления, их среднее.

import math

hudshee = 1
for k in range(1, 9):
    monetka = 1 - 0.5 ** k
    lp = 1 - (1 - 1 / k) ** k
    srednee = (monetka + lp) / 2
    hudshee = min(hudshee, srednee)
    print(k, round(monetka, 3), round(lp, 3), round(srednee, 3))
print(round(1 - 1 / math.e, 3), hudshee)

1 0.5 1.0 0.75
2 0.75 0.75 0.75
3 0.875 0.704 0.789
4 0.938 0.684 0.811
5 0.969 0.672 0.821
6 0.984 0.665 0.825
7 0.992 0.66 0.826
8 0.996 0.656 0.826
0.632 0.75

На скобках из одного литерала монетка даёт 0,5, округление - 1: среднее 0,75. На скобках из двух - обе по 0,75. Дальше монетка растёт к единице, округление падает к 0,632, а среднее сначала растёт до 0,826 и потом медленно убывает к (1 + 1 − 1/e) / 2 ≈ 0,816. Наименьшее среднее - 0,75, достигается на длинах 1 и 2. Каждый способ в одиночку проваливается: монетка до 1/2 на единичных скобках, округление до 0,632 на длинных. Вместе - не ниже 3/4.

Есть и лучшие алгоритмы: полуопределённое программирование даёт для MAX-2SAT около 0,94. А для формул, где во всех скобках ровно по три литерала, монетка с её 7/8 оказывается пределом возможного - об этом глава о пределах приближенияРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: PCP и карта границ: где простые алгоритмы оказались лучшими возможными.

Что ломается без этого

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

Одно округление на всех. Длинные скобки, и округление проигрывает монетке: 0,66 против 0,99 на семи литералах.

Случайный ответ в продакшене. Ожидание 15,37 - это среднее; конкретный бросок может дать 12. Метод условных ожиданий даёт гарантированный набор не хуже ожидания, без лотереи.

Повторяющиеся литералы. Анализ предполагает, что в скобке разные переменные. (x ∨ x) - на деле скобка длины 1, и для монетки она выполняется с вероятностью 1/2, а не 3/4.

Зачем это в работе

Несовместные требования встречаются в конфигурациях, расписаниях, подборе параметров: все сразу не выполнить, и вопрос - как выполнить побольше. MAX-SAT с весами - стандартная модель для этого, у неё есть отдельные решатели. Но и простой рецепт этого урока работает на миллионах скобок, если при фиксации переменной пересчитывать ожидание только по скобкам, где она встречается: решить релаксацию, два раза посчитать ожидание по формуле, зафиксировать переменные по одной. Гарантия 3/4 - и нижняя граница для отчёта в придачу: релаксация говорит, сколько требований нельзя выполнить ни при каком наборе.

Теперь сам

1. Скобка из четырёх литералов. С какой вероятностью её выполнит монетка?
2. В скобке (x₁ ∨ x₂) релаксация дала y₁ = y₂ = 0,5, z = 1. С какой вероятностью её выполнит округление?
3. Почему лучший из двух ответов не хуже их среднего?