Смешанное целочисленное линейное программирование для ограничения ранжирования

Question

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

• У меня есть X1, X2, X3, X4 в качестве переменных решения.
• Существует ограничение, требующее определить i как ранг X1 (например, если X1 является наибольшим числом среди X1, X2, X3, X4, то i=1; если X1 является вторым по величине числом, то i=2, если X1 - третье по величине число, тогда i=3, иначе i=4)

Как я мог записать это ограничение в смешанное целочисленное линейное программирование?

Answer 1

Не просто. Вот попытка:

Сначала введите двоичные переменные y(i) за i=2,3,4

Тогда мы можем написать:

 x(1) >= x(i) - (1-y(i))*M   i=2,3,4
 x(1) <= x(i) + y(i)*M       i=2,3,4
 rank = 4 - sum(i,y(i))
 y(i) ∈ {0,1}                i=2,3,4

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

Небольшой пример иллюстрирует это работает:

----     36 VARIABLE x.L  

i1 6.302,    i2 8.478,    i3 3.077,    i4 6.992


----     36 VARIABLE y.L  

i3 1.000


----     36 VARIABLE rank.L                =            3.000