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.
87
questions
0
votes
0
answers
16
views
Resources about Busacker & Gowen algorithm
I have a relatively hard time understanding the Busacker & Gowen algorithm. I could not
find any resources on it, contrary to Ford-Fulkerson method that is described in Comen's "Introduction ...
- 113
2
votes
1
answer
51
views
Shortest path problem with time as a random variable with correlation
I'm trying to solve the $\alpha$-reliable shortest path problem with correlated time variables (travel time per arc), i.e. the shortest path subject to the constraint that the probability of arriving ...
- 30.3k
0
votes
1
answer
72
views
Interpret the formulation of a pricing model in crowdshipping
I am trying to run the pricing model from the paper "Designing pricing and compensation schemes by integrating matching and routing models for crowd-shipping systems" on python with Gurobi, ...
CommunityBot
- 1
2
votes
2
answers
128
views
Transportation Problem
I want to create a transportation model. I have identified importing and exporting countries with their estimated demand and supply. The cost of transportation per one uni is already calculated for ...
CommunityBot
- 1
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 ...
- 103
0
votes
1
answer
410
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 ...
- 1,275
0
votes
0
answers
56
views
What the dual constraints mean?
I have a primal problem that is a network-flow:
$$
min_x \sum_{a \in A} c_a x_a \\
\text{s.t.} \sum_{a \in A:n = v} X_{a}-\sum_{a \in A:n' = v} X_{a} = \begin{cases} \;\;\;1, \; v=n^{in} \\ -1, \; v=n^...
- 507
0
votes
0
answers
29
views
When Supply < Demand - distributing resources v/s meeting as much demand
In network modelling LP , when Supply < Demand and we use normal balance of flow rule for all the constraints, i.e. (inflow - outflow) <= supply or demand, we say we are trying to redistribute ...
3
votes
1
answer
349
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 ...
- 2,587
4
votes
0
answers
761
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-...
- 2,587
3
votes
0
answers
70
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,885
1
vote
2
answers
248
views
Graph models - Maximum flow problem and minimum cost flow problem
I'm trying to solve this problem:
An investment agency holds the rights to six investment projects: I1, I2, ..., I6. Projects I1, I2 and I3 are research and
technological development projects and the ...
- 3,343
2
votes
2
answers
266
views
Improve Network Flow computation with additional Pyomo constraints based on previous computation
I am performing several max-flow computations on extremely similar networks and I seek to improve their execution time based on information from previous computations (As there is a lot of repetitive ...
- 3,343
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 ...
3
votes
2
answers
119
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 ...
- 30.3k
3
votes
2
answers
111
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 ...
- 3,343
2
votes
1
answer
98
views
Modify the network model to accommodate multiple vehicles
Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is ...
- 37.8k
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,885
2
votes
1
answer
60
views
Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem
At page 7 from these slides there is a Greedy algorithm I want to implement.
It says
let $P_i$ be the shortest path (if one exists) that [...]
connects some ($s_j$, $t_j$) pair that is not yet ...
- 30.3k
5
votes
1
answer
184
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 ...
- 30.3k
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.
- 30.3k
1
vote
0
answers
95
views
Assignment problem with continuous constraints
I am trying to solve an assignment problem where all the variables are continuous. I have a set of sources S, and another set of destinations D. Each source and destination have capacity/demand ...
- 30.3k
3
votes
1
answer
120
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 ...
- 1,885
3
votes
1
answer
82
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 ...
- 168
6
votes
1
answer
377
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 ...
- 1,885
-1
votes
1
answer
88
views
Assignment Problem with continuous decision variable
I have to solve a problem from industry where there are a number of machines which should be assigned to a number of tasks. The difference from the general assignment problem is tough, that the ...
- 136
1
vote
1
answer
149
views
Help with dual of a problem
Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot.
$s$ is the source node and $t$ the sink node.
I'm uncertain if the last dual constraint in ...
- 30.3k
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.
...
- 1,885
2
votes
1
answer
574
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 ...
- 30.3k
0
votes
1
answer
110
views
How to model a simple routing problem using nodes and arcs
I have the following problem.
I have a route which begins at node $0$.
I want to begin and end in $0$ which is a depot.
Now in this route even customer will be visited in order for example customer 2 ...
- 30.3k
3
votes
4
answers
518
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 ...
- 313
1
vote
0
answers
150
views
How to see fix constraint violations found with IIS
I'm running a simple MCNF model to see if my network is balanced. I'm using Gurboi in Python and with the IIS I can see that there are 2 constraint violations making it infeasible. How do I fix these ...
- 30.3k
4
votes
2
answers
172
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-...
- 37.8k
1
vote
0
answers
597
views
How to eliminate large matrix coefficients and large RHS warning in Gurobi
I'm solving a large network flow problem using Gurobi to do Benders decomposition in Python. The imported .csvs contain values that typically fall in either zero, the range of [20,200], or with a ...
- 109
3
votes
2
answers
532
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 ...
- 37.8k
2
votes
2
answers
214
views
Min cut network for patients
I'm trying to formulate a min cut algorithm
There are two classes of patients: 1, 2, and the maximum number of patients that can be assigned to each bed per day is shown below as well.
$$
\begin{array}...
- 67
4
votes
1
answer
188
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 ...
- 1,885
6
votes
2
answers
311
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.
...
- 12.9k
3
votes
0
answers
134
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 ...
- 5,341
3
votes
0
answers
107
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 ...
2
votes
1
answer
345
views
How to solve a minimum cost flow problem with time constraints
In the following picture, the decision-maker has to make deliveries to node $V=\{1,2,3,4,5,6\}$. He has two options: use cars or bikes. In both cases, he has to make a stop at a relay point where the ...
- 115
1
vote
0
answers
22
views
Asserting solution existence via approximation of multi-commodity integral flow
Consider a polynomial $\epsilon$-approximation for MCF with integral flow (like the one based on LP relaxation).
Can I (in general) use this algorithm as a predicate, asserting whether a solution ...
- 561
3
votes
1
answer
93
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. ...
- 30.3k
5
votes
1
answer
162
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 ...
- 30.3k
3
votes
0
answers
186
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 ...
- 561
1
vote
0
answers
66
views
Multi-commodity flow problem reduction
Assume to tackle a particular group of instances for the integral multi-commodity flow problem.
Particularly, given a digraph $G = (V \cup S \cup T,E)$, such that $S, T, V$ are all disjoint. ...
- 561
1
vote
0
answers
45
views
Solving a max-flow problem through lex-max flow problem
Assume that, for a given network, its multi-sink multi-source max-flow satisfies a lexicographic order. Is this enough to state that I can solve the max-flow problem, by using a lex-max solver (i.e. a ...
- 561
1
vote
0
answers
22
views
Complexity of lexicographic integral flow
I read that the lexicographic flow problem is polynomially solvable. However it allows for continuous flow values.
Is there any reference about the problem with integral flow (and its complexity)?
- 561
1
vote
2
answers
397
views
How to include material flow in job shop scheduling problem (as constraint?)?
I am reading about https://en.wikipedia.org/wiki/Job-shop_scheduling and https://en.wikipedia.org/wiki/Optimal_job_scheduling. Such scheduling is possible if we know the number (amount) of operations (...
- 37.8k
1
vote
0
answers
27
views
Is there a difference between "Integral Quickest Transshipment" and "Integral Quickest Multicommodity flow"?
I can't get the difference between this two problems, which seem equal to me.
But, for the former, a polynomial solver is known, while, for the latter, it is not.
EDIT - References:
...
- 561