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.
24
questions with no upvoted or accepted answers
6
votes
0
answers
97
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
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
5
votes
0
answers
675
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
4
votes
0
answers
770
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-...
- 392
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,198
3
votes
0
answers
135
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
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 ...
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
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
2
votes
0
answers
35
views
Lexicographic flow property and consequences
I am struggling with the understanding of the (quite famous) paper on lexicographical flows:
Maximal, Lexicographic, and Dynamic Network Flows - by Edward Minieka
...
- 561
2
votes
0
answers
249
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
0
answers
150
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
1
vote
0
answers
29
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 ...
- 123
1
vote
0
answers
98
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 ...
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 ...
- 109
1
vote
0
answers
599
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
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
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
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
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, ...
0
votes
0
answers
57
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 ...
