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

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