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
6
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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.
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
0answers
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
...
2
votes
0answers
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)
$$
\...
1
vote
0answers
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 ...
1
vote
0answers
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. ...
1
vote
0answers
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 ...
1
vote
0answers
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)?
1
vote
0answers
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:
...
1
vote
0answers
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}
...
0
votes
0answers
90 views
struggling to understand why this is a bi-objective function
i am working on a network-design problem. Where Containerflow between 2 Origin-Destination-Port-Pairs has to be fullfilled via some hub-ports. Sure, you want to pick a hub-port based on the distance, ...
0
votes
0answers
58 views
Different ways to model node switching (Flow on/off) in network flow problem
I would like to model a network flow problem in which there are some pipelines and valves. I would like to model valves in the problem. The valves let flow run or stop just like the on/off switch. One ...