Отсечения Гомори: убрать дробную вершину, сохранив целые

Если понимаешь, почему округляется неравенство, а не точка - переходи к «Теперь сам».

Как думаешь: почему дробная вершина вообще мешает?

Переменная означает число купленных устройств. Релаксация выдаёт 7/3 устройства, стоимость прекрасна, но такое решение поставить в стойку нельзя. Округление вниз может нарушить обязательный объём, вверх - бюджет или ограничение ресурса. Требуется изменить область поиска так, чтобы убрать невозможную точку и сохранить все реализуемые варианты.

Слишком сильное неравенство может случайно удалить настоящий оптимум. Поэтому главное обязательство отсечения - корректность для каждого допустимого целого решения. То, что оно «улучшило границу» на одном примере, этого не доказывает.

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

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

Механизм: дробные части строки

Рассмотрим чисто целочисленную задачу в стандартной форме. Все участвующие переменные - неотрицательные целые, включая базисную x_B и небазисные x_j. В строке симплексной таблицы записано x_B + Σ a_j x_j = b. В текущей базисной точке все небазисные переменные нулевые, поэтому x_B = b. Если b дробное, точка не является целочисленным решением.

Обозначим f(t) = t − floor(t) - дробную часть. Она всегда лежит между нулём включительно и единицей исключительно; например, f(−0,2) = 0,8, потому что округление вниз даёт минус один. Разделим коэффициенты и правую часть на целую и дробную части. Получим x_B + Σ floor(a_j)x_j − floor(b) = f(b) − Σ f(a_j)x_j.

Левая часть целая. Правая не больше f(b) < 1, поскольку x_j ≥ 0 и дробные части коэффициентов неотрицательны. Значит, целая левая часть не больше нуля. После переноса получаем дробное отсечение Гомори: Σ f(a_j)x_j ≥ f(b). В текущей дробной вершине левая часть ноль, правая положительна; вершина отрезана. Для любого неотрицательного целого решения исходной строки вывод сохраняется, поэтому оно не потеряно.

Условия здесь существенны. Если какая-то x_j непрерывная, целочисленность левой части больше не следует. Для смешанного целочисленного программирования используют другие, смешанные отсечения. Если переменная свободна по знаку, её сначала корректно преобразуют. Если строка записана с другой стороной знака, коэффициенты надо привести к объявленной форме, а не механически копировать формулу.

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

Правило

Корректное отсечение сохраняет все допустимые целые точки и исключает хотя бы одну дробную точку релаксации. Для строки x_B + Σa_j x_j = b с неотрицательными целыми переменными дробное отсечение: Σf(a_j)x_j ≥ f(b). Дробная часть считается через округление вниз, в том числе для отрицательных коэффициентов.

Разбор: точка 7/3 отрезается, целый оптимум остаётся

Возьмём строку x_B + x₁/2 + x₂/3 = 7/3. Максимизируем x_B. Релаксация достигает 7/3 при нулевых x₁,x₂. Отсечение после умножения на шесть имеет вид 3x₁ + 2x₂ ≥ 2. Переберём все целые решения: из неотрицательности верхние границы переменных следуют непосредственно из строки.

from fractions import Fraction
from itertools import product
from math import floor


def drobnaya(x):
    return x - floor(x)


b = Fraction(7, 3)
a = [Fraction(1, 2), Fraction(1, 3)]
resheniya = []
for x1, x2 in product(range(5), range(8)):
    xb = b - a[0] * x1 - a[1] * x2
    if xb >= 0 and xb.denominator == 1:
        levaya = drobnaya(a[0]) * x1 + drobnaya(a[1]) * x2
        assert levaya >= drobnaya(b)
        resheniya.append((int(xb), x1, x2))
print('релаксация:', b)
print('целый оптимум:', max(x[0] for x in resheniya))
print('все целые решения проходят:', len(resheniya))
print('дробная вершина проходит:', Fraction(0) >= drobnaya(b))
print('дробная часть -1/5:', drobnaya(Fraction(-1, 5)))
print('оптимальные целые:', [x for x in resheniya if x[0] == 2])

релаксация: 7/3
целый оптимум: 2
все целые решения проходят: 6
дробная вершина проходит: False
дробная часть -1/5: 4/5
оптимальные целые: [(2, 0, 1)]

Точка (2,0,1) удовлетворяет строке: 2 + 1/3 = 7/3. Она проходит отсечение с равенством. Точка (7/3,0,0) удовлетворяет релаксации, но нарушает отсечение. Таким образом, новая область меньше старой, а целый оптимум сохранён. Рациональная арифметика в программе нужна, чтобы ошибку округления float не принять за математическое нарушение.

Разбор: почему нельзя округлить все коэффициенты вниз

Из неравенства x/2 + y/2 ≤ 3/2 для целых x,y следует x + y ≤ 3, а вовсе не 0x + 0y ≤ 1. Последняя строка хоть и верна, но совершенно бесполезна. В общем случае округление коэффициентов может быть и неверным, если не соблюдены знаки переменных. В отсечении выводится целочисленность целого выражения, после чего округляется его граница; отдельные числа не округляются произвольно.

Для чисто целочисленной строки с отрицательным a_j особенно легко перепутать остаток и усечение к нулю. У −1/5 дробная часть 4/5, а не −1/5. Второе значение разрушило бы неотрицательность суммы, на которой держится доказательство.

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

Сильное численное улучшение не оправдывает неверное отсечение. Использование формулы чисто целочисленной задачи при непрерывных переменных способно удалить допустимый ответ. Тысячи почти параллельных отсечений могут ухудшить численную устойчивость и увеличить время решения. Поэтому решатель отбирает сечения, а не добавляет всё, что удалось вывести.

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

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

Теперь сам

Строка чисто целочисленной задачи: x_B + (2/3)x₁ + (1/4)x₂ = 5/2, все переменные неотрицательны. Выпиши дробное отсечение без дробей.