Questions tagged [network-flow]

For questions related to the formulation or solution methodologies of network flow problems. Some of the well-known network flow problems are maximum flow problem, minimum-cost flow problem, and multi-commodity flow problem.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
66 views

Demonstrating a given solution is basic for a MCFP?

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 ...
58 views

Complexity of solving a certain commodity flow problem

Does anyone know the complexity of obtaining the optimal solution to the integral multi-commodity network flow problem with unit demands, integral capacities, but the cost of using an arc varies ...
265 views

Solver for Go Programming Laguage

Has anyone used MIP solvers (open source or commercial) with Go language https://golang.org/? I am looking for a solver for simple linear MIPs for network flows and set cover types of problems.
87 views

Sources of Min-Cost Flow Models That Utilize Binary Variables for Transportation Networks

I am looking for articles that include min-cost flow models with binary variables for flow transportation like gas networks, traffic systems, heating systems. Is there any specific place(like OR ...
73 views

Availability of library for solving generalized network flow problems

I need to solve a large-scale generalized network flow problem. For reference, it is a pure network-flow model with the exception that arcs have a positive coefficient applied to flow on them. In my ...
169 views

Multi-commodity (Integral) flow problem with unit demand; complexity

It seems to me that a multi-commodity flow problem should be treated differently when the commodity demand constraint is an equivalence and not a lower-bound. Consider a unit demand. Apparently, in ...
69 views

Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
26 views

Lexicographic flow property and consequences

I am struggling with the understanding of the (quite famous) paper on lexicographical flows: Maximal, Lexicographic, and Dynamic Network Flows - by Edward Minieka ...
121 views

Solving transportation problem by the Network Simplex

I am trying to solve the following problem using Network Simplex method. But I have questions. My attempt: Basis Matrix$(B)$ Rows: 1, 2, 3, 4, 5 Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5)  \...
22 views

Asserting solution existence via approximation of multi-commodity integral flow

Consider a polynomial $\epsilon$-approximation for MCF with integral flow (like the one based on LP relaxation). Can I (in general) use this algorithm as a predicate, asserting whether a solution ...
30 views

Multi-commodity flow problem reduction

Assume to tackle a particular group of instances for the integral multi-commodity flow problem. Particularly, given a digraph $G = (V \cup S \cup T,E)$, such that $S, T, V$ are all disjoint. ...
22 views

Solving a max-flow problem through lex-max flow problem

Assume that, for a given network, its multi-sink multi-source max-flow satisfies a lexicographic order. Is this enough to state that I can solve the max-flow problem, by using a lex-max solver (i.e. a ...
20 views

Complexity of lexicographic integral flow

I read that the lexicographic flow problem is polynomially solvable. However it allows for continuous flow values. Is there any reference about the problem with integral flow (and its complexity)?
23 views

Is there a difference between "Integral Quickest Transshipment" and "Integral Quickest Multicommodity flow"?

I can't get the difference between this two problems, which seem equal to me. But, for the former, a polynomial solver is known, while, for the latter, it is not. EDIT - References: ...
103 views

Simplex - Network flow problem : Arc from 1 to P with infinite capacity

The Network - Maximum flow problem below aims to find the maximum flow using simplex method : With the LP as follow : LP : \begin{Bmatrix} Z(Max) = \sum_{i=1}^{m} fi \\ Af =0 \end{Bmatrix} ...