# 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.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
745 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.
105 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 ...
• 253
63 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 ...
• 1,583
1k views

### Google-OR tools vs Pyomo and other commercial Solvers for solving a simple maximum flow problem

I have implemented a Pyomo model for solving maximum flow problem as a subroutine of an algorithm. However, the approach does not scale very well because Pyomo does not provide a very good way to re-...
• 390
77 views

### Flow problem with flow demands

Recently I found a subproblem in a project I am working with. This problem is a sort of flow variant, as you will see. And I am looking for literature-related articles and also fast approaches for ...
142 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 ...
• 105
118 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 ...
196 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 ...
152 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 ...
• 181
31 views

### How to formulate / solve a multi-commodity flow problem with dependent flow between commodities to plan harvesting operations

I am working on a multi-commodity flow problem to conduct tactical harvesting planning. The idea is to model the crop and the machinery as commodities. Crop move from field to being harvested and ...
• 21
42 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 ...
286 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)  \...
• 97
162 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} ...
• 125
1 vote
58 views

### Reference request for different network types

I am trying to understand the mathematical models used in airline revenue management when a disruption occurs. The researchers are re-scheduling the resources(aircraft, flights etc.) in recovery ...
• 61
1 vote
43 views

### Network flow problem to minimize differences between nodes

What type of algorithm should I be researching to solve the following problem? Each node has a potential that is a function (linear or non linear) of the net flow in/out of that node. Nodes are ...
1 vote
37 views

### How to convert unit-capacity network flow into transportation problems?

I am working on a problem that can be modeled as a minimum-cost network flow problem where the capacity of edges is 1. I found Exercise 3.8, Chapter 5 of Parallel and Distributed Computation: ...
1 vote
68 views

• 1