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

41 questions
Filter by
Sorted by
Tagged with
87 views

I'm trying to explore OR problems and wanted to know what algorithm fits here. Consider fuel stations with lithium ion battery that service replacing battery at each refuel ( you replace your batters ...
93 views

### Multi-commodity flow (or path selection) 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 ...
87 views

### Extreme points for capacitated flow polytope

Given a network as a directed acyclic graph with a source and sink, and non-negative edge capacities, I am interested in the extreme source-sink flows. More formally, I am interested in a ...
114 views

### Problems modeling a constraint in network design problem

I'm working on a network design problem where the objective is to minimise the network design cost. Given a graph G = (V, E) and a set of point-to-point demands K, the task is to route the demands and ...
60 views

### Max-flow of undirected graph

I know that a max flow problem for undirected graphs has a standard reduction to directed graphs in order to apply Ford–Fulkerson algorithm and getting a feasible solution. Here's my doubt. An ...
121 views

### Best way to add dummy to transportation problem? Zero cost will be always chosen first?

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ...
163 views

### How to model this multi-commodity flow problem with a twist?

Problem description I am working on a variation of the multicommodity flow problem on a graph $G=(V,E)$. I have requests $r_{uv}$ for pairs of nodes $(u,v), u\in V, v\in V$, which means that $r_{uv}$ ...
443 views

### How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
65 views

57 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 ...
95 views

### How can I find the shortest path for all nodes in a graph from a source $s$?

This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination. The idea behind this model is that we assign a flow of 1 for ...
61 views

### Algorithm / Method for determining N nodes to disconnect group of nodes

Hell everyone I have been trying to read through this forum for the methodology to approach a graph/network problem. The idea is I have an undirected graph, and every node is capable of talking to any ...
89 views

### Combined arc capacity constraints in network flows

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce ...
90 views

### Max flow problem with piece-wise costs

This question is a variant of a question I posted earlier and also fixes some typos in the earlier post (Complexity \ Reference request for variant of max flow problem). Some of the changes are ...
72 views

### Complexity \ Reference request for variant of max flow problem

In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the ...
59 views

### Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
54 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 ...
79 views

### Find minimum cost problem

The problem below aims to find the minimum cost for the network architecture: We want to build a network where client terminals are connected to servers by cabling which is very expensive. The network ...
101 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} ...
140 views

### shortest path problem,I want to write constraints in closed form

the constraints in the photo ,I need to translate to the closed-form I don't know how can I do this. Can you help? I need to write the mod file and dat file in Cplex for this problem
142 views

### Maximum Flow Problem : Can someone refer me to accessible valuable resources

Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
184 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.
1k views

### How do we call this problem in literature and how to model it?

I have a set of sources and a set of sinks. Each source $s$ can produce a set of different products $P_s$. The transportation inter-sources and inter-sinks are allowed. The sources do not ...
59 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 ...
282 views

### Max flow problem without splitting the flow from the supply nodes - LP formulation help

Since max flow formulation can be easily solved using LP, I wanted to ask the following: I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The ...
226 views

### Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
341 views

### Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
When creating a network flow formulation you can set up sinks with integer flow requirement $\ge 1$. This yields solutions with the total amount of flow along an edge. I have also seen this as a ...