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
0 votes
1 answer
65 views

Inconsistencies in modeling a binary variable that indicates a switch

this is a follow-up question to this post here and to @RobPratt's answer. I have implemented the whole thing, and now it happened that on day 1 the machine did not run and was only used for the first ...
0 votes
0 answers
29 views

Spectral clustering with laplacian matrix eigenvector

I want to separate a given graph in $k$ clusters with the laplacian matrix ($L = D-A$ where $D$ is the degree matrix and $A$ the adjacency matrix). How can the eigenvectors of $L$ be used, along with ...
1 vote
1 answer
58 views

Reference request for different network types

I am trying to understand the mathematical models used in airline revenue management when a disruption occurs. The researchers are re-scheduling the resources(aircraft, flights etc.) in recovery ...
0 votes
0 answers
40 views

Network formulation based side constraints for a workforce scheduling problem

For a workforce scheduling problem, I have formulated the "at most one shift per day" constraint as a network formulation based side constraint (with other constraints like demand coverage, ...
1 vote
1 answer
68 views

Fast Algorithms for Min-cost Multicommodity Flow Problem with Most Arcs Having 0 cost

I have a min-cost multicommodity flow problem with the following characteristics: Flows can be fractional (integer flows not required) Set of commodity types is $K$, set of demand nodes is $\\{ d_k : ...
1 vote
0 answers
43 views

Network flow problem to minimize differences between nodes

What type of algorithm should I be researching to solve the following problem? Each node has a potential that is a function (linear or non linear) of the net flow in/out of that node. Nodes are ...
2 votes
0 answers
31 views

How to formulate / solve a multi-commodity flow problem with dependent flow between commodities to plan harvesting operations

I am working on a multi-commodity flow problem to conduct tactical harvesting planning. The idea is to model the crop and the machinery as commodities. Crop move from field to being harvested and ...
1 vote
0 answers
37 views

How to convert unit-capacity network flow into transportation problems?

I am working on a problem that can be modeled as a minimum-cost network flow problem where the capacity of edges is 1. I found Exercise 3.8, Chapter 5 of Parallel and Distributed Computation: ...
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 ...
1 vote
0 answers
94 views

Numerical infeasibility for moving numbers along some specific conversion edges to get maximal number on target node from some starter node

I have a problem that can be represented as an optimization problem. Sometimes, solver engines report infeasible depending on the parameters I have at hand. The root cause is numeric ranges. ...
1 vote
1 answer
178 views

Lagrangian Relaxation Lower Bound exceeds the Upper bound and the Optimal solution

I'm trying to minimize an MIP model employing a Lagrangian relaxation approach. However, I've encountered an issue where, in certain instances, the lower bound (resulting from the Lagrangian sub-...
1 vote
2 answers
123 views

Capacited Vehicle Routing Problem with flow formulations

I'm trying to solve the CVRP based on flow-formulation. In such a model, we have a decision variable with two-index, $x_{ij}$, where I'm using the MTZ formula to eliminate sub-tours. We have then a ...
1 vote
1 answer
143 views

Column generation for solving minimum cost multicommodity flow problem with additional edge disjoint constraints

I'm working on an integer programming problem that's fundamentally a minimum cost multicommodity flow (MCMF) problem with additional constraints. I'm exploring the use of column generation to solve it,...
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 ...
0 votes
1 answer
111 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, ...
1 vote
0 answers
79 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 ...
-1 votes
1 answer
108 views

Grocery Store Problem

I have an issue with my Excel function for a grocery store problem and I am not sure where I messed up the constraints. I have the value of the solution it should be (cost = 8,283). I need to make a ...
2 votes
1 answer
55 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 ...
2 votes
2 answers
137 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 ...
6 votes
1 answer
801 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 ...
0 votes
1 answer
451 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 ...
3 votes
1 answer
441 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 ...
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-...
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 ...
1 vote
2 answers
274 views

Graph models - Maximum flow problem and minimum cost flow problem

I'm trying to solve this problem: An investment agency holds the rights to six investment projects: I1, I2, ..., I6. Projects I1, I2 and I3 are research and technological development projects and the ...
2 votes
2 answers
328 views

Improve Network Flow computation with additional Pyomo constraints based on previous computation

I am performing several max-flow computations on extremely similar networks and I seek to improve their execution time based on information from previous computations (As there is a lot of repetitive ...
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 ...
3 votes
2 answers
151 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 ...
3 votes
2 answers
131 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 ...
2 votes
1 answer
100 views

Modify the network model to accommodate multiple vehicles

Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is ...
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-...
2 votes
1 answer
61 views

Find the shortest path connecting some (s,t) - a greedy (?) criterion to a multi-commodity flow problem

At page 7 from these slides there is a Greedy algorithm I want to implement. It says let $P_i$ be the shortest path (if one exists) that [...] connects some ($s_j$, $t_j$) pair that is not yet ...
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 ...
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.
1 vote
0 answers
117 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 ...
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 ...
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 ...
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 ...
-1 votes
1 answer
104 views

Assignment Problem with continuous decision variable

I have to solve a problem from industry where there are a number of machines which should be assigned to a number of tasks. The difference from the general assignment problem is tough, that the ...
1 vote
1 answer
157 views

Help with dual of a problem

Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot. $s$ is the source node and $t$ the sink node. I'm uncertain if the last dual constraint in ...
4 votes
1 answer
242 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. ...
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 ...
0 votes
1 answer
112 views

How to model a simple routing problem using nodes and arcs

I have the following problem. I have a route which begins at node $0$. I want to begin and end in $0$ which is a depot. Now in this route even customer will be visited in order for example customer 2 ...
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 ...
1 vote
0 answers
155 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 ...
4 votes
2 answers
181 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-...
1 vote
0 answers
766 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 ...
3 votes
2 answers
657 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 ...
2 votes
2 answers
217 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}...
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 ...