3
$\begingroup$

I am working with multi-commodity flow at integral flow with unit demand for each operation.

Since I use the MCF formulation to model path finding, in my scenario cycles are just a waste of resources. I often read that MCF models path finding problems, without making particular assumptions on the graph (which in my case is undirected).

However, I can't see why an MCF solver shouldn't send a flow within a cycle to maximize the objective function, even in my scenario with unit demand.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Traditionally, the objective of the multicommodity flow problem is to minimize cost. The usual situation that the costs are positive naturally avoids cycles. The same idea arises with the shortest path problem: if the costs are positive, there are no negative cycles and an LP solver returns a path rather than a path plus cycles.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot, I do agree. However, an LP solver works on continuous flows while it gives no particular approximation bound for the integral case, isn't it? $\endgroup$
    – Daniele Cuomo
    Oct 13, 2021 at 15:36
  • $\begingroup$ I mean, there might even be a feasible continuous solution, while an integral flow doesn't exist. $\endgroup$
    – Daniele Cuomo
    Oct 13, 2021 at 15:46
  • 2
    $\begingroup$ For an integer multicommodity problem with a minimization objective, an LP relaxation provides a lower bound on the optimal objective value. I don't know whether that yields any approximation for the upper bound, like it does for set covering (for example). $\endgroup$
    – RobPratt
    Oct 13, 2021 at 16:35
  • $\begingroup$ In other words, assume $\epsilon \in [0,1]$ being the lower-bound. The LP solver gives a solution which can't be worse than $f^{OPT}*\epsilon$? Also, if $f^{OPT}$ doesn't exist, the LP solver will give empty solution. $\endgroup$
    – Daniele Cuomo
    Oct 13, 2021 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.