Min-cost-max-flow со знаком в целевой функции

Question

У меня есть какая-то проблема Min-cost-max-flow с простыми уравнениями баланса в ограничениях, но с "плохим" знаком в целевой функции, т.е. целевая функция зависит только от наличия потока вдоль края, а не от его значения.

Я могу ввести переменную bool U_i ограничение U_i <= x_i и переписать целевую функцию с помощью U_i, но это смешанная целочисленная модель программирования. В моих реальных данных число переменных должно быть не менее 10000 и число строк ограничений также составляет около 10000.

Q1: слишком медленно использовать простой метод ветвления и вырезания?

В2: Существуют ли уловки для решения этой проблемы с сохранением линейности модели? (Я думаю, что ответ нет)

В3: Итак, есть ли эффективные подходы для решения этой проблемы?

Answer 1

1. Обычно ограничение для двоичных файлов выглядит как

   x(i) <= y(i)*capacity(i)

   для дуги i, где x(i) - поток, а y(i) ∈ {0,1}. Это моделирует значение

   y(i)=0 => x(i)=0

2. Многие (но не все) модели со структурой сети могут быть быстро решены даже после добавления целочисленных ограничений. Вы действительно должны попробовать это (что является лучшим ответом на большинство вопросов о производительности). Простые модели с бинарными переменными 10 КБ автоматически не выходят за пределы допустимого диапазона. Используйте хороший MIP решатель.