Skip to main content

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
17 votes
1 answer
358 views

Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
Nike Dattani's user avatar
  • 1,278
12 votes
1 answer
1k views

How do we call this problem in literature and how to model it?

I have a set of sources and a set of sinks. Each source $s$ can produce a set of different products $P_s$. The transportation inter-sources and inter-sinks are allowed. The sources do not ...
Antarctica's user avatar
  • 2,917
8 votes
1 answer
162 views

References for "metric" network flow problems

Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems. Very efficient implementation of state-...
Stefano Gualandi's user avatar
7 votes
2 answers
463 views

Max flow problem without splitting the flow from the supply nodes - LP formulation help

Since max flow formulation can be easily solved using LP, I wanted to ask the following: I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The ...
prakash gawas's user avatar
6 votes
2 answers
323 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. ...
anerjee's user avatar
  • 119
6 votes
1 answer
390 views

How to Model Path Being Only Through Adjacent Cells

I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real ...
Raghav Thakar's user avatar
6 votes
1 answer
456 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.) ...
Pramesh Kumar's user avatar
6 votes
1 answer
798 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 ...
Jacob Myer's user avatar
6 votes
1 answer
104 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 ...
batwing's user avatar
  • 1,583
6 votes
1 answer
94 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 ...
funky_capybara's user avatar
6 votes
0 answers
744 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
6 votes
0 answers
105 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
4 answers
1k 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 ...
bsha's user avatar
  • 81
5 votes
3 answers
1k views

Fast algorithm for Transportation Problem in Python?

The Transportation Problem can be solved with a simplex algorithm, but it's time-consuming. I'm wondering if there exists a specific Python-implemented algorithm with low complexity.
dgamboz's user avatar
  • 135
5 votes
1 answer
172 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 ...
Daniele Cuomo's user avatar
5 votes
1 answer
897 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,...
Khalilbs's user avatar
5 votes
1 answer
323 views

What is the impact of making flow fractional rather than integer?

When creating a network flow formulation you can set up sinks with integer flow requirement $\ge 1$. This yields solutions with the total amount of flow along an edge. I have also seen this as a ...
fhk's user avatar
  • 1,069
5 votes
1 answer
162 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 ...
dxb's user avatar
  • 1,799
5 votes
1 answer
208 views

Flow problem with side constraints: how to eliminate subtours?

I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
Kuifje's user avatar
  • 13.5k
5 votes
1 answer
286 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}$ ...
Kuifje's user avatar
  • 13.5k
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,583
4 votes
2 answers
225 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$$ $...
KGM's user avatar
  • 2,377
4 votes
2 answers
160 views

Maximum Flow Problem : Can someone refer me to accessible valuable resources

Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
JirenOppaik's user avatar
4 votes
1 answer
769 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 ...
user620842's user avatar
4 votes
2 answers
179 views

How to fix unbalanced multi-commodity network flow with equal supply and demand?

I have a fairly large network with eleven commodities and arc capacities that are commodity-dependent (i.e. an arc may have a higher capacity for one commodity than another). I'm solving a protection-...
Emma Kuttler's user avatar
4 votes
1 answer
190 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 ...
crypto's user avatar
  • 143
4 votes
1 answer
242 views

Can we add a certain binary row to a matrix which preserves total unimodularity?

Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
graphtheory123's user avatar
4 votes
1 answer
557 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 ...
Daniele Cuomo's user avatar
4 votes
1 answer
712 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 ...
Daniele Cuomo's user avatar
4 votes
1 answer
1k 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 ...
learnPyt's user avatar
4 votes
1 answer
241 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. ...
yingqi's user avatar
  • 43
4 votes
1 answer
189 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 ...
batwing's user avatar
  • 1,583
4 votes
0 answers
1k 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
  • 390
3 votes
4 answers
550 views

How to see constraint violation for network flow problem

I am testing to see if my network is balanced as part of a larger protection-interdiction-restoration problem. To do this, I'm solving the problem as a minimum cost network flow problem to see if the ...
Emma Kuttler's user avatar
3 votes
2 answers
652 views

Designing a multi-commodity network flow optimizer

I'm trying to solve multi commodity multi source network flow optimization problem using Python-PuLP. Here is how my problem looks like: The numbers on the arcs represent the order of priority a ...
themlchic's user avatar
3 votes
1 answer
100 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. ...
Daniele Cuomo's user avatar
3 votes
2 answers
150 views

Partial Lagrangian in the Max-Flow problem

In the question: "Partial" Lagrangian Dual in LP It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter ...
Cris's user avatar
  • 143
3 votes
2 answers
130 views

Transportation problem with consolidation within path

There's a supply network design problem that I'm trying to solve, which is as follows: A certain amount of goods need to be transported from point A to B, and can have stoppages in between with a ...
J. Alan's user avatar
  • 31
3 votes
1 answer
125 views

Modeling a special case of conservation of flow

At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e The first requirement is that only one of the two inflow ...
Mike's user avatar
  • 717
3 votes
1 answer
437 views

Minimum cost flow problem with multiple arcs between nodes in Python / Google OR

Is it possible to work with multiple arcs between 2 nodes within Google OR? Or are there better modeling techniques? I want to optimize flow from supply to demand areas, where supply and demand are ...
Fabian's user avatar
  • 31
3 votes
1 answer
90 views

Reformulating undirected to directed edges for MCF

As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges. By quoting them: The ...
Daniele Cuomo's user avatar
3 votes
1 answer
146 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 ...
batwing's user avatar
  • 1,583
3 votes
1 answer
219 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 ...
fathese's user avatar
  • 423
3 votes
0 answers
77 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
142 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
118 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
194 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
152 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
1 answer
580 views

Model the TSP as a shortest path

We have a directed graph $G=(N,A)$ where $N$ are the verticies $N=0,1,2,3,4,5,..,n$ the starting location is node 0. For each arc $a=i-j$ in A we have a distance $d_a>0$ So we want to start and ...
Fernando Martinez's user avatar
2 votes
1 answer
111 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 ...
S moran's user avatar
  • 335