Целлюлоза и монеты или КБК: что означает вес SOS?

Question

При определении задачи смешанного целочисленного линейного программирования с использованием целлюлозы можно определить sos следующим образом:

x1 = LpVariable('x1', cat = LpInteger)
x2 = LpVariable('x2', cat = LpInteger)
prob.sos1['sos'] = x1 + 2*x2

("sos", или специально упорядоченный набор, является специальным ограничением, определяющим, что только одна переменная в наборе может быть ненулевой).

Мы видим, что это позволяет задавать весовые коэффициенты для переменных sos (в данном случае 1,2). Предположительно они определяют приоритет каждой переменной, то есть какие переменные должны быть первыми отличными от нуля при ветвлении.

Но как именно определяются веса?

Основным решателем является монета-или-КБК, и я не смог ничего найти о том, как они используют веса SOS.

Answer 1

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

Веса в SOS2 часто необходимы для указания порядка (SOS2 имеет понятие соседей). SOS1 не имеет этой проблемы.

Наконец, если у вас хорошие границы, бинарные переменные часто лучше, чем переменные SOS1. Решатели лучше ограничивают и генерируют лучшие сокращения при использовании бинарных переменных. Мое правило: если вы можете сформулировать структуру SOS1 с двоичными переменными, используя хорошие значения big-M, используйте двоичные переменные. Если вы не можете найти хорошие значения big-M, рассмотрите SOS1.