# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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, ...
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 ...
712 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 ...
414 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 ...
57 views

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 ...
312 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. ...
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 ...
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 ...
346 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 ...
1 vote
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 ...
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. ...
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 ...
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 ...
1 vote
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. ...
1 vote
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 ...
1 vote
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)?
1 vote