A multi-commodity flow problem is defined like this:
https://www.wikiwand.com/en/Multi-commodity_flow_problem
I am considering a optimization problem in which there are no demands on each commodity, but the minimum of (F1,F2,F3...Fn) is maximized. Fi (i=1,2,...,n) is the flow from each commodity.
I want to do this since I hope there will be no shortcoming for my network. The performance of my network is concerned with the minimum flow from the commodities, thus I want to maximize it.
I think it would be a NP-hard problem but I can't fully prove it. Can anyone provide me some advice about how to solve it? I will be really appreciated about it.
https://www.wikiwand.com/en/Multi-commodity_flow_problem
I believe such problem is considered NP-hard only for integer flow. For fractional/real valued flows you can always use algorithms for linear programming (simplex methods or interior-point methods in particular). This much is also mentioned in solution section of the link you gave.
Another note is that you can reduce your min-max problem to the demand problem by a bisection method: for a given d you can check whether there is a feasible solution to your problem with demands di = d; by applying bisection method you can find the maximum value of d with accuracy eps by solving log(1/eps) multicomodity demand problems.
Hi, Nikolai V. Malkovskii
You are right, I am sorry that I did't express my question exactly. In my problem , I consider a integer flow.
I have found some papers for developing heuristic ways to solve it, like this paper:
I will try to use this way to solve my problem.
https://scholar.google.com/scholar?hl=zh-CN&q=Greening+Backbone+Networks%3A+Reducing+Energy+Consumption+by+Shutting+Off+Cables+in+Bundled+Links&btnG=&lr=
- Badges
- Science topic