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
Filter by
Sorted by
Tagged with
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 ...
Johnny Bueti's user avatar
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 ...
batwing's user avatar
  • 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.
Alexey Sorokin's user avatar
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-...
Pia MiA's user avatar
  • 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 ...
Matheus Diógenes Andrade's user avatar
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 ...
asdf's user avatar
  • 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 ...
Suleyman Karabuk's user avatar
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 ...
Daniele Cuomo's user avatar
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 ...
WindBreeze's user avatar
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 ...
Daniele Cuomo's user avatar
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) $$ \...
diabolik's user avatar
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} ...
JirenOppaik's user avatar
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 ...
satk0's user avatar
  • 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 ...
PrashanthVajjhala's user avatar
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 ...
Emma Kuttler's user avatar
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 ...
Emma Kuttler's user avatar
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 ...
Daniele Cuomo's user avatar
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. ...
Daniele Cuomo's user avatar
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 ...
Daniele Cuomo's user avatar
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)?
Daniele Cuomo's user avatar
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: ...
Daniele Cuomo's user avatar
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, ...
Last_Mile's user avatar
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^...
orpanter's user avatar
  • 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 ...
user2705034's user avatar