6
$\begingroup$

Given a minimum-cost flow problem, how could I go about demonstrating that a specific solution (as sets of basic and non-basic (!) arcs that build a rooted spanning tree for a given graph) is basic and feasible for the problem?

Update: the MCF problem has a variable number of divergences, for the nodes – some require more flow than others, some generate it and through the remaining ones the flow only transit. Also, how does proving the feasibility of a solution and whether or not it is basic change with and without bound constraints?

As per the feasibility, I figure it could be pretty straightforward: a solution is feasible as long as it satisfies all constraints, I may dare saying for any Operation Research problem.

For a MCF problem, as long as the strongly connected graph built with the arcs in the given solution create a rooted spanning tree free of any cycles, I would claim the solution is indeed feasible.

How about proving the given solution is basic, however?

Given a linear problem, a solution is basic if it is indeed possible to build a matrix $B \subset A$ ($A$ being the matrix of technological coefficients) with at least $m$ (where $m$ is the number of constraints for the given LP) linearly independent columns. Since the network simplex works similarly to the "classical" simplex, would the statement above be sufficient to prove a solution is indeed basic?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ If you can verify that 1) $B x_B + N x_N = b$, 2) $x_N$ are on a bound, and 3) $B$ is nonsingular then you primal basis. You also have to prove $B^\top y = c_B$, $c_N-N^\top y \ge 0$ if it should be dual basis too. $\endgroup$
    – ErlingMOSEK
    Jan 16, 2020 at 17:39
  • $\begingroup$ We need to know more about the MCF problem to validate some of your statements. Is there a single source node? Is there one sink or are there multiple sinks? Do the arcs have capacity limits? $\endgroup$
    – prubin ♦
    Jan 16, 2020 at 21:55
  • $\begingroup$ @prubin Updated the question, I felt I had forgotten something – thank you. $\endgroup$
    – Johnny Bueti
    Jan 16, 2020 at 22:52
  • $\begingroup$ Regarding bounds, I think that your assertion about the chosen arcs creating a cycle-free rooted spanning tree being sufficient for feasibility is untrue when arcs have capacity limits. $\endgroup$
    – prubin ♦
    Feb 2, 2020 at 23:00
  • 1
    $\begingroup$ Erling's comment is the straightforward approach to proving that the solution is basic, assuming you are okay with writing out the coefficient matrix for the system of flow equations. I think that trying to prove that it is basic without using the matrices would turn into solving another flow problem (proving that there is no nontrivial incremental flow possible that has volume zero on all basic arcs). $\endgroup$
    – prubin ♦
    Feb 2, 2020 at 23:08

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.