Pulp & coin-or-cbc: Что означают веса SOS?

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

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

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

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

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

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


coin-or-cbc mixed-integer-programming linear-programming integer-programming pulp
person Ant6n    schedule 15.09.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

person Erwin Kalvelagen    schedule 16.09.2018
comment
Да, похоже, я не могу заставить SOS положительно повлиять на мои проблемы, где уже есть ограничение sum(bin_var_i, i=0..n) = 1. Это и для cbc-coin-or, и для гуроби. Я думаю, вы правы, что SOS - это скорее запасной вариант, когда для переменных неизвестны верхние границы. - person Ant6n; 19.09.2018