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?

  • 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$ Jan 16 '20 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 '20 at 21:55
  • $\begingroup$ @prubin Updated the question, I felt I had forgotten something – thank you. $\endgroup$ Jan 16 '20 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 '20 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 '20 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.