Преобразование условного устранения CVRP в нормальные

Question

Я пытаюсь исключить , если условия ограничивают из следующей формулировки CVRP.

Я попробовал несколько больших методов М на бумаге, но не смог придумать правильную переформулировку.Не могли бы вы помочь мне найти решение?

Спасибо!

Answer 1

Вы можете разбить уравнение на два неравенства и применить метод big-M:

ui + qj <= uj + M(1-xij)
ui + qj >= uj - M(1-xij)

Модели с константами big-M обычно бывают слабыми и численно нестабильными, поэтому я предлагаю выбрать константукак можно меньше (т. е. сделать так, чтобы M зависело от ij, если это возможно).Чтобы узнать больше об этом, взгляните на Опасности "Big M" .