Какие весы использовать в специальных упорядоченных наборах?

Question

В настоящее время я работаю над проблемой MIP, где я могу воспользоваться специальными упорядоченными наборами типа 2 (SOS2).

Моя проблема в том, что я не совсем понял такие наборы. Причина этого - из-за весов, которые мне приходится присваивать переменным в моем SOS2.

Я не уверен, что именно я должен назначить. В моем наборе есть довольно четкий порядок, но я не уверен, какие весы должны быть и просто назначить 1,2,3 ... n не так, я думаю?

Итак, мой вопрос: может ли кто-нибудь объяснить мне, какие веса переменных в специальных упорядоченных множествах и какие значения они должны быть назначены?

Answer 1

Прежде всего, они определяют порядок. Специально для наборов SOS2 существует концепция соседа: в наборе SOS2 только две соседние переменные могут быть неотрицательными. Некоторые решатели также используют веса в своем решении ветвления. Это может быть полезно, если у вас есть значения x, такие как (1,2,3,10000). Поэтому проконсультируйтесь со своей документацией. В общем случае весы должны быть уникальными. Использование (1,2,3,...) часто является хорошим дефолтом, в противном случае используйте что-то вроде значений x (если у вас нет сегмента, параллельного оси y).

Обратите внимание, что формулировка с бинарными переменными во многих случаях превосходит формулировку SOS (особенно это относится к высокопроизводительным решателям, которые могут применять умные сокращения в формулировках с двоичными переменными). Некоторые решатели даже попытаются автоматически переформулировать некоторые SOS-множества в форму с использованием двоичных переменных.