# 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.

86 questions
Filter by
Sorted by
Tagged with
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 ...
71 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, ...
120 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 ...
49 views

293 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. ...
132 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 ...
99 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 ...
303 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 ...
89 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. ...
152 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 ...
1 vote
55 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
44 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
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: ...
423 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 ...
1 vote
395 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 (...
31 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 ...
687 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,...
126 views

I'm trying to explore OR problems and wanted to know what algorithm fits here. Consider fuel stations with lithium ion battery that service replacing battery at each refuel ( you replace your batters ...
183 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 ...
127 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 ...
185 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 ...