Минимальный поток затрат с минимальными инвестиционными затратами

Question

Я хочу использовать Python Min-Cost Flow решатель, чтобы иметь возможность строить новые сети.Это означает, что у меня есть исходный полный граф с вершинами, являющимися либо поставщиками, либо имеющими спрос.Использование алгоритма должно сказать мне, исходя из их стоимости, какие грани будут использоваться для удовлетворения всех требований.В отличие от существующих проблем, стоимость ребра при использовании описывается не только удельной стоимостью, но также имеет вложение этого ребра, которое не зависит от потока.Я изучал исходный код networkx и or-tools, но не могу понять, как адаптировать их для реализации инвестиционных затрат по краям.У кого-нибудь есть идея получше или она может помочь мне адаптировать код?

С наилучшими пожеланиями, Юстус

Answer 1

Вы не можете решить эту проблему с помощью стандартного алгоритма графа (например, MinCostFlow).Вместо этого вам нужно сформулировать это как смешанную целочисленную программу.Вы можете начать с этого примера:

https://developers.google.com/optimization/assignment/assignment_mip

Но вам нужно немного его настроить: вам нужно два класса переменных решения: invest_var (двоичный) и flow_var(непрерывное).Цель будет выглядеть следующим образом:

min: sum(flow_cost[i,j]*flow_var[i,j]) + sum(invest_cost[i,j]*invest_var[i,j])
And you need to add an additional constraint for each link:
flow_var[i,j] <= BIG_INT * invest_var[i,j]

Цель этого ограничить flow_var до 0, если invest_var равно 0.Ограничения спроса и предложения будут такими же, как в примере.BIG_INT является константой.Вы можете установить его следующим образом:

BIG_INT=max(flow_upper_bound[i,j])

Где flow_upper_bound - это верхняя граница для ваших переменных flow_var.

Обратите внимание, что теперь проблема становится смешанной целочисленной линейной программой, а не просто линейнойПрограмма.