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.
103
questions
17
votes
1
answer
362
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,278
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,927
8
votes
1
answer
163
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,750
7
votes
2
answers
479
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
6
votes
2
answers
341
views
Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution
For a logistics optimization problem I am working on, the most natural expression of the problem is using a node-arc formulation of the MCNF. It is solved using an LP/MIP solver like CPLEX/Gurobi.
...
- 119
6
votes
1
answer
393
views
How to Model Path Being Only Through Adjacent Cells
I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real ...
- 325
6
votes
1
answer
466
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
6
votes
1
answer
833
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
6
votes
1
answer
105
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,583
6
votes
1
answer
96
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
6
votes
0
answers
782
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.
- 141
6
votes
0
answers
108
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
5
votes
4
answers
1k
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
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
5
votes
1
answer
176
views
(Integral) multi-commodity flow on undirected graph
Usually in (integral) multi-commodity flow problems the graph is assumed to be directed. Instead, I am working with an undirected graph. Is it possible to transform it in a digraph?
Does such a ...
- 571
5
votes
1
answer
959
views
pyomo/ipopt: nonlinear network optimization not converging
The question (very short version)
Why can I not decrease the lower boundary for the decision variable model.v_dot (see implementation) below 30 ? As soon as I do so,...
- 53
5
votes
1
answer
324
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
5
votes
1
answer
166
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,809
5
votes
1
answer
219
views
Flow problem with side constraints: how to eliminate subtours?
I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
- 13.7k
5
votes
1
answer
307
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}$ ...
- 13.7k
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,583
4
votes
2
answers
227
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,397
4
votes
2
answers
160
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
4
votes
1
answer
789
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
4
votes
2
answers
188
views
How to fix unbalanced multi-commodity network flow with equal supply and demand?
I have a fairly large network with eleven commodities and arc capacities that are commodity-dependent (i.e. an arc may have a higher capacity for one commodity than another). I'm solving a protection-...
- 109
4
votes
1
answer
190
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 ...
- 143
4
votes
1
answer
246
views
Can we add a certain binary row to a matrix which preserves total unimodularity?
Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
- 246
4
votes
1
answer
586
views
Is Multicommodity Flow problem really NP-hard?
Within paper ON THE COMPLEXITY OF TIMETABLE AND MULTI-COMMODITY FLOW PROBLEMS
there's a proof that the multi-commodity is NP-hard.
While in ...
- 571
4
votes
1
answer
731
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 ...
- 571
4
votes
1
answer
1k
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 ...
- 49
4
votes
1
answer
248
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
4
votes
1
answer
191
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,583
4
votes
0
answers
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
3
votes
4
answers
553
views
How to see constraint violation for network flow problem
I am testing to see if my network is balanced as part of a larger protection-interdiction-restoration problem. To do this, I'm solving the problem as a minimum cost network flow problem to see if the ...
- 109
3
votes
2
answers
703
views
Designing a multi-commodity network flow optimizer
I'm trying to solve multi commodity multi source network flow optimization problem using Python-PuLP. Here is how my problem looks like:
The numbers on the arcs represent the order of priority a ...
- 59
3
votes
1
answer
105
views
Does multi-commodity flow problem (MCF) block cycling flows?
I am working with multi-commodity flow at integral flow with unit demand for each operation.
Since I use the MCF formulation to model path finding, in my scenario cycles are just a waste of resources. ...
- 571
3
votes
2
answers
154
views
Partial Lagrangian in the Max-Flow problem
In the question:
"Partial" Lagrangian Dual in LP
It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter ...
- 143
3
votes
2
answers
142
views
Transportation problem with consolidation within path
There's a supply network design problem that I'm trying to solve, which is as follows:
A certain amount of goods need to be transported from point A to B, and can have stoppages in between with a ...
- 31
3
votes
1
answer
127
views
Modeling a special case of conservation of flow
At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e
The first requirement is that only one of the two inflow ...
- 793
3
votes
1
answer
485
views
Minimum cost flow problem with multiple arcs between nodes in Python / Google OR
Is it possible to work with multiple arcs between 2 nodes within Google OR?
Or are there better modeling techniques?
I want to optimize flow from supply to demand areas, where supply and demand are ...
- 31
3
votes
1
answer
91
views
Reformulating undirected to directed edges for MCF
As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges.
By quoting them:
The ...
- 571
3
votes
1
answer
152
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 ...
- 1,583
3
votes
1
answer
225
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 ...
- 423
3
votes
0
answers
78
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 ...
- 1,240
3
votes
0
answers
145
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
3
votes
0
answers
125
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 ...
3
votes
0
answers
199
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 ...
- 571
3
votes
0
answers
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
2
votes
1
answer
584
views
Model the TSP as a shortest path
We have a directed graph $G=(N,A)$ where $N$ are the verticies $N=0,1,2,3,4,5,..,n$ the starting location is node 0.
For each arc $a=i-j$ in A we have a distance $d_a>0$
So we want to start and ...
2
votes
1
answer
113
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 ...
- 335