특별 주문 세트에는 어떤 중량을 사용합니까?

Question

현재 MIP 문제에 대해 연구 중이며, 유형 2 (SOS2)의 특별 주문 세트를 이용할 수 있습니다.

내 문제는 내가 그런 세트를 완전히 이해하지 못했다는 것입니다. 그 이유는 내 SOS2의 변수에 할당해야하는 가중치 때문입니다.

정확히 무엇을 지정해야하는지 잘 모르겠습니다. 내 세트에는 꽤 명확한 순서가 있지만, 나는 가중치가 있어야하고 단지 1,2,3 ...을 할당하는 것이 확실하지 않습니다. n은 정확하지 않습니까?

제 질문은 특별 주문 세트의 변수의 가중치와 할당 된 값을 설명해 줄 수 있습니까?

Answer 1

먼저 주문을 정의합니다. 특히 SOS2 세트의 경우 이웃이라는 개념이 있습니다. SOS2 세트에서는 두 개의 인접 변수 만이 음수가 될 수 없습니다. 일부 솔버는 분기 결정에 가중치를 사용합니다. (1,2,3,10000)과 같은 x 값을 가진 경우 유용 할 수 있습니다. 그러므로 솔버 문서를 참조하십시오. 일반적으로 sos 가중치는 고유해야합니다. (1,2,3,...)을 사용하면 좋은 기본값이되며 그렇지 않으면 x 값과 같은 것을 사용합니다 (y 축에 평행 한 선분이 없다고 가정).

많은 경우 이진 변수가있는 수식이 SOS 수식보다 우수한 성능을 보입니다 (특히 바이너리 변수가있는 수식에 스마트 컷을 적용 할 수있는 고급 솔루션의 경우). 일부 솔버는 자동으로 일부 SOS 세트를 이진 변수를 사용하여 양식으로 재구성하려고 시도합니다.