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

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.

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