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

86 questions
Filter by
Sorted by
Tagged with
262 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}$ ...
923 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 ...
149 views

145 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 ...
408 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 ...
106 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 ...
153 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 ...
179 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 ...
101 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 ...
90 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 ...
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 vote
147 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 ...
1k views

### Fast algorithm for Transportation Problem in Python?

The Transportation Problem can be solved with a simplex algorithm, but it's time-consuming. I'm wondering if there exists a specific Python-implemented algorithm with low complexity.
149 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} ...
498 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
156 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.
672 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 ...
95 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 ...
426 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 ...
333 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 ...
709 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 ...