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.
6
questions with no upvoted or accepted answers
6
votes
0answers
54 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
96 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.
4
votes
0answers
48 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 ...
3
votes
0answers
47 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
68 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
82 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}
...
