Using arcs with fixed costs in min-cost flow?

[Hershel Safer]

I have a min-cost flow network in which some arcs have a fixed charge, that is, if arc k has non-zero flow x_k, then the cost is c_k, independent of the amount of flow. A flow of 0 incurs 0 cost. These arcs do not have capacity constraints.

I know how to model this as a mixed integer program (MIP): Add a 0/1 variable y_k with cost c_k. Set the capacity on arc k to M * y_k, where M is the sum of all supplies. So the fixed cost is incurred if and only if the arc has flow.

Can this be solved using a min-cost flow formulation, which would be more efficient than a general MIP implementation? Does OR-Tools (or any other package) have an extension to min-cost flow that accommodates this?

Cross-posted to StackOverflow.

Thanks, Hershel

[Bruno De Backer]

Hi Hershel, 

(I read the answer on StackOverflow and this seems like an idea to try.)

The min-cost flow algorithm that we provide in OR-tools does not take fixed costs into account.

I thought of a way where you would duplicate the arcs, but there is no way to force the algorithm to use the "fixed-cost" arc with one-unit capacity before the other arcs. 

Finally, I found this abstract https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230190304 . Hochbaum is well-known in the LP/flow community, and he claims that the problem of min-cost flow with fixed cost on the arcs is NP-hard. Bad luck. 

So there is actually no way that we could improve our algorithm to take into account fixed costs (I would really have loved to), unless P=NP. I leave the proof of the latter to the reader ;-)

By the way, can I ask what kind of problem you're tackling to have such an NP-hard min-cost flow?

Cheers, and thank you for using our tools.

BdB

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0d07b7ef-b4bf-49ee-bcd1-d9a24d3d6dbdn%40googlegroups.com.

--

BdB