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.

Filter by
Sorted by
Tagged with
2
votes
2answers
189 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}...
0
votes
0answers
90 views

struggling to understand why this is a bi-objective function

i am working on a network-design problem. Where Containerflow between 2 Origin-Destination-Port-Pairs has to be fullfilled via some hub-ports. Sure, you want to pick a hub-port based on the distance, ...
6
votes
2answers
192 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. ...
3
votes
0answers
89 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 ...
0
votes
0answers
58 views

Different ways to model node switching (Flow on/off) in network flow problem

I would like to model a network flow problem in which there are some pipelines and valves. I would like to model valves in the problem. The valves let flow run or stop just like the on/off switch. One ...
3
votes
0answers
73 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
1answer
115 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
0answers
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 ...
3
votes
1answer
67 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. ...
5
votes
1answer
83 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
0answers
30 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
0answers
23 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
0answers
20 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
0answers
23 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: ...
3
votes
1answer
212 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
2answers
342 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 (...
2
votes
0answers
26 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 ...
3
votes
1answer
164 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,...
2
votes
1answer
100 views

Advanced Transportation optimization problem

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 ...
3
votes
0answers
170 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 ...
3
votes
1answer
90 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 ...
4
votes
1answer
166 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 ...
4
votes
1answer
85 views

Max-flow of undirected graph

I know that a max flow problem for undirected graphs has a standard reduction to directed graphs in order to apply Ford–Fulkerson algorithm and getting a feasible solution. Here's my doubt. An ...
3
votes
1answer
235 views

Best way to add dummy to transportation problem? Zero cost will be always chosen first?

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ...
5
votes
1answer
177 views

How to model this multi-commodity flow problem with a twist?

Problem description I am working on a variation of the multicommodity flow problem on a graph $G=(V,E)$. I have requests $r_{uv}$ for pairs of nodes $(u,v), u\in V, v\in V$, which means that $r_{uv}$ ...
5
votes
4answers
523 views

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
2
votes
1answer
76 views

Constraining flow into a node and out of a node using Min Cost Flow input

Let's say I have a graph $G=(V,E)$ where each vertex has an edge going both into and out of it (i.e. cyclic, akin to the kidney donor pair problem). Now suppose we have a capacity $u_{ij} = 1 \forall(...
3
votes
1answer
206 views

Min Cost Flow with lower bound reduction to MCF algorithm

We define the Min Cost Flow Problem with Lower Bounds (MCFPLB) as a generalization of the usual Min Cost Flow. The input consists of: a directed graph $G=(V,E)$ capacities $u_{ij} \geq 0$ for each ...
1
vote
1answer
127 views

Solving general minimum cost flow problems using only one demand and one supply node

This is a practice in using reduction. Suppose I have a solver that only allows input to a MCF that specifies only one demand and one supply node. How could I use this solver to solve general MCF ...
1
vote
1answer
314 views

Python Gurobipy Maximum Flow: How to model "source" and "sink" in constraints

I am attempting to capture the nature of a "source" node as well as a "sink" node where the net flow for each node aside from the source and sink is zero. Here is my code so far: <...
0
votes
1answer
58 views

Adding slack nodes to min cost network flows

I have the following question. I want to clarify couple of points. As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is: Do we need to ...
2
votes
0answers
122 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) $$ \...
2
votes
1answer
59 views

Maximum flow minimum cut

For the following problem I am trying to find maximum flow and minimum cut: I found the maximum flow as 6 like this: $1-3-7-8:2 flows$ $1-2-5-8: 2 flows$ $1-3-4-5-8:1 flow$ $1-3-4-6-5-8:1 flow$ But I ...
0
votes
1answer
112 views

Minimum cost flow problem with negative cost arcs

As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc ...
6
votes
1answer
231 views

Extreme point and extreme ray of a network flow problem

"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) ...
4
votes
1answer
82 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. ...
0
votes
1answer
699 views

How to describe the traveling salesman problem with an integer programming model?

I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal ...
3
votes
1answer
91 views

What is the difference between min- cut formulation and (bi) partitioning formulation?

I have a min-cut formulation and a bi-partitioning problem. The two problems focus on finding the minimal cut value separating the two partitions? So what are really the differences between the ...
4
votes
2answers
211 views

How to solve this convex problem heuristically?

I have the following problem $$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$ $$\text{subject to}$$ $$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$ $...
3
votes
0answers
70 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 ...
0
votes
1answer
167 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 ...
2
votes
1answer
78 views

Algorithm / Method for determining N nodes to disconnect group of nodes

Hell everyone I have been trying to read through this forum for the methodology to approach a graph/network problem. The idea is I have an undirected graph, and every node is capable of talking to any ...
5
votes
1answer
101 views

Combined arc capacity constraints in network flows

Consider the network flow polyhedron for a directed graph $G = (N, A)$. Along with the standard flow-balance and single-arc capacity constraints, we are faced with additional constraints which enforce ...
4
votes
1answer
110 views

Max flow problem with piece-wise costs

This question is a variant of a question I posted earlier and also fixes some typos in the earlier post (Complexity \ Reference request for variant of max flow problem). Some of the changes are ...
6
votes
1answer
81 views

Complexity \ Reference request for variant of max flow problem

In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the ...
6
votes
1answer
63 views

Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
5
votes
0answers
58 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
vote
1answer
85 views

Find minimum cost problem

The problem below aims to find the minimum cost for the network architecture: We want to build a network where client terminals are connected to servers by cabling which is very expensive. The network ...
1
vote
0answers
103 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} ...
2
votes
1answer
195 views

shortest path problem,I want to write constraints in closed form

the constraints in the photo ,I need to translate to the closed-form I don't know how can I do this. Can you help? I need to write the mod file and dat file in Cplex for this problem