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
5
votes
1
answer
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}$ ...
- 12.9k
5
votes
4
answers
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 ...
- 81
2
votes
1
answer
149
views
Constraining flow into a node and out of a node using Min Cost Flow input
Let's say I have a graph $G=(V,E)$ where each vertex has an edge going both into and out of it (i.e. cyclic, akin to the kidney donor pair problem). Now suppose we have a capacity $u_{ij} = 1 \forall(...
- 271
4
votes
1
answer
674
views
Min Cost Flow with lower bound reduction to MCF algorithm
We define the Min Cost Flow Problem with Lower Bounds (MCFPLB) as a generalization of the usual Min Cost Flow. The input consists of:
a directed graph $G=(V,E)$
capacities $u_{ij} \geq 0$ for each ...
- 271
1
vote
1
answer
209
views
Solving general minimum cost flow problems using only one demand and one supply node
This is a practice in using reduction. Suppose I have a solver that only allows input to a MCF that specifies only one demand and one supply node. How could I use this solver to solve general MCF ...
- 271
1
vote
1
answer
1k
views
Python Gurobipy Maximum Flow: How to model "source" and "sink" in constraints
I am attempting to capture the nature of a "source" node as well as a "sink" node where the net flow for each node aside from the source and sink is zero. Here is my code so far:
<...
- 271
0
votes
1
answer
255
views
Adding slack nodes to min cost network flows
I have the following question. I want to clarify couple of points.
As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is:
Do we need to ...
- 97
2
votes
0
answers
239
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
2
votes
1
answer
152
views
Maximum flow minimum cut
For the following problem I am trying to find maximum flow and minimum cut:
I found the maximum flow as 6 like this:
$1-3-7-8:2 flows$
$1-2-5-8: 2 flows$
$1-3-4-5-8:1 flow$
$1-3-4-6-5-8:1 flow$
But I ...
- 97
0
votes
1
answer
443
views
Minimum cost flow problem with negative cost arcs
As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc ...
- 97
6
votes
1
answer
408
views
Extreme point and extreme ray of a network flow problem
"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) ...
- 411
4
votes
1
answer
219
views
splittable multicommodity problem with CPLEX
I am working on a splittable multicommodity flow problem, where each commodity can be split into $k$ orders. However, I don't know the value of $k$ in advance. Here is my code.
...
- 43
0
votes
1
answer
760
views
How to describe the traveling salesman problem with an integer programming model?
I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal ...
- 181
3
votes
1
answer
202
views
What is the difference between min- cut formulation and (bi) partitioning formulation?
I have a min-cut formulation and a bi-partitioning problem.
The two problems focus on finding the minimal cut value separating the two partitions?
So what are really the differences between the ...
- 413
4
votes
2
answers
222
views
How to solve this convex problem heuristically?
I have the following problem
$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$
$$\text{subject to}$$
$$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$
$...
- 2,211
3
votes
0
answers
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 ...
- 181
0
votes
1
answer
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 ...
- 181
2
votes
1
answer
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 ...
- 325
5
votes
1
answer
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 ...
- 1,799
4
votes
1
answer
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 ...
- 1,458
6
votes
1
answer
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 ...
- 1,458
6
votes
1
answer
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 ...
- 103
5
votes
0
answers
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,458
1
vote
1
answer
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 ...
- 73
5
votes
3
answers
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.
- 135
2
votes
0
answers
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}
...
- 125
2
votes
1
answer
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
- 21
4
votes
2
answers
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.
- 125
5
votes
0
answers
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.
- 131
12
votes
1
answer
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 ...
- 2,907
6
votes
0
answers
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 ...
- 253
7
votes
2
answers
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 ...
- 173
17
votes
1
answer
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 ...
- 1,268
6
votes
1
answer
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 ...
- 447
8
votes
1
answer
160
views
References for "metric" network flow problems
Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems.
Very efficient implementation of state-...
- 1,740
5
votes
1
answer
287
views
What is the impact of making flow fractional rather than integer?
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 ...
- 1,069