# Tag Info

## Hot answers tagged network-flow

12

Your first case can be modeled as a minimum cost flow problem. You can split sinks with demands for more than one type into as many nodes as there are demanded types; make copies of incident arcs accordingly (this step results in sinks that have exactly one type of demand). split source nodes $i$ into copies $i'$ and $i''$, connect the copies with an arc $(... 10 To enforce$x_{i,j} > 0 \implies y_{i,j} = 1$, you can impose a linear big-M constraint $$x_{i,j} \le (|V|-1) y_{i,j}.$$ This TSP formulation is described in Application 16.2 of Ahuja, Magnanti, and Orlin, Network Flows. 9 This is a minimum cost flow problem in the bipartite graph$G=(V,A)$with$V=N_U \cup N_B$. Add a source node and link it to each vertex$v\in N_U$. On each of these arcs, constrain the flow to be in the range$[a_{min},a_{max}]$. Note that if$a_{min} > |N_B|$the problem is infeasible. Likewise with a sink node, that you link to each vertex$v \in N_B$, ... 6 I believe this result (with proof) is contained in the text book "Network Flows" by Ahuja, Magnati and Orlin. In particular, chapter 11 is on the Network Simplex algorithm and Theorems 11.2 and 11.3 are about optimal solutions in the form of spanning trees. The proofs use the structure of the dual solutions, and also use previous results, so it's ... 6 Here is one suggestion : Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, Orli. The maximum flow problem is delt with in chapters 6-8, but I suggest you read the ones before if you are not familiar with flows in general. Also, James Orlin (one of the authors, teaches at MIT) has a webpage where you can find solutions to some of the ... 6 If you are simply normalizing the demand, then you are essentially solving the same problem. I would argue that the main benefit of integer capacities is from the modeling viewpoint. When solving a maximum flow problem, for example, having integer capacities in the arcs implies that every optimal basic solution satisfies integrality. Hence, if you have an ... 6 Graph cuts were mainly used in computer vision, where since 2011 deep neural networks have taken over the field. The decline from 2015 on is attributable to a time delay in picking up neural networks. Specifically, graph cuts were used for inferring maximum probable states in Markov Random Fields (MRF), with input costs coming from hand-tuned features. ... 5 These are called Generalized Upper Bound (GUB) constraints. 5 Dijkstra's algorithm finds a shortest path from$s$to all other nodes in$N \setminus\{s\}. The corresponding linear programming problem is to minimize $$\sum_{(i,j)\in A} c_{i,j} x_{i,j}$$ subject to $$\sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} = \begin{cases} n-1 &\text{for i=s}\\ -1 &\text{for i\in N \setminus \{s\}} \end{cases}... 5 Introduce a supersource node s, a supersink node t, arcs from s to each source, and arcs from each sink to t. Arc (s,i) has zero cost and capacity equal to supply[i]. Arc (i,t) has zero cost and capacity equal to -supply[i]. All original nodes have supply zero, s has supply equal to the sum of positive supplies, and t has supply equal to ... 4 Whether you need a dummy node to absorb excess flow depends on the method you are using for solving the problem. (For instance, if you are using an LP model then you do not need the dummy node.) If you do need it, one dummy node will suffice. You assign it demand = excess supply and run a zero-cost arc from each supply node to the dummy node. No other ... 4 If you define binary variables for each of the arcs let's say$$m_{ij} \ \ \forall i\in \text{supply}\ \ \text{and} \ \ j \in \text{demand}$$then you can add the following constraint to the model:$$\sum_j m_{ij} = 1$$and the shipment then can be limited as the following (M is a large number to relax s_{ij} if necessary):$$s_{ij} \le M \cdot m_{ij}... 4 Add binary variables y_{ai} and the following constraints: \begin{align} y_{ax}+ y_{ay} + y_{za} &\le 1\\ x_{ai} &\le 4 y_{ai} \end{align} 4 Here is a link that includes all the information that you need. The matrix should include all the capacity limitations on all the connections between nodes. Actually, for your example, it should be a 8\times8 matrix with all the coefficients. Each row represents one of the constraints in your LP model. In other words for each row, you consider one of the ... 4 Introduce a supersource node s that is adjacent to all sources and a supersink node t that is adjacent to all sinks, and then solve the minimum s-t node cut problem on the resulting graph. 4 i would assume, that there doesn't even exist an optimal solution. You want to have \epsilon-flow across every edge to collect all the cost b_{uv}. On the other hand you want to maximize the flow across the edges with the highest cost c_{uv}. This leads to pressure to have \epsilon as small as possible, while still \epsilon > 0. Such an \... 3 You can rewrite the maximum cost flow problem with objective\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$$as a minimum cost flow problem with objective$$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$for the concave function$g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} ...

3

There is a well-studied problem close to your one: Integral Flow With Multipliers. It was proved to be NP-hard in the seminal Sartaj Sahni's paper in computational complexity theory (see section 2.2 of the paper). Another interesting, more recent paper can be found here.

3

The following references do not completely answer the idea of a metric (that satisfies the triangle inequality) as said by the OP they are still useful. Under network flow, Emami (2018) describes several algorithms that can be used to tackle the geometric transportation problem. The exact geometric algorithm The main contribution of this paper is that, ...

3

A group of undergraduate students at Berkeley have a fantastic reading group on topics in TCS, and they are currently reading Max Flow. They have a webpage where they've curated recent papers with progress on the problem.

2

In OPL to get the shortest path you could use: .mod tuple edge { key int o; key int d; int weight; } {edge} edges=...; {int} nodes={i.o | i in edges} union {i.d | i in edges}; int st=1; // start int en=8; // end dvar int obj; // distance dvar boolean x[edges]; // do we use that edge ? minimize obj; subject to { obj==sum(e in edges) x[e]*e....

2

Roughly speaking, in minimum cut problems, the goal is generally to find a minimum cut (possibly weighted) between two fixed sets of vertices, called the sources and the sinks. Given one source and one sink in input, the problem can be solved in polynomial time, a famous theorem in combinatorial optimization. On the other hand, in graph partitioning problems,...

2

Now that you have removed the range constraints, the problem decomposes by $j$ and can be solved optimally for each $j$ by a greedy algorithm: set $X_{i,j}=1$ for the $b_\max$ largest (positive) values of $R_{i,j}$.

2

One way to model this is to add a dummy arc from the sink to the source and impose flow balance of 0 at every node, including the source and sink. But if you prefer the conditional constraint, I think the proper syntax is: m.addConstrs( (flow.sum('*',j) - flow.sum(j,'*') == 0 for j in vertices if j != 2 and j != 7), "node")

2

I think that there might be a straightforward approach here that requires only solving a linear program. Consider the LP arc-flow formulation of multi-commodity network flow; I won't repeat it here since it is very well known. The solution is expressed by flow variables $x^b_{ij}$, the flow of commodity $b$ on network directed arc $(i,j)$. Based on your ...

2

The maximum flow is $6$. To find a corresponding minimum cut, note that $S=\{1,3,4,7\}$ is the set of nodes reachable from the source node $1$ in the residual network. Now consider the arcs from $S$ to $N\setminus S$.

1

No, making the change you describe could make the problem infeasible, as you observed for this instance. Instead, just think of the negative cost as a reward. If using the arc will reduce the overall cost, then the solver will exploit that.

1

Your problem description is quiet vague. So i picked the simplest solution to his problem i can think off in modeling language JuMP. If you are more detailed about the reality you are working with a better model can be chosen. clients = 24 servers = 3 using JuMP using GLPK class = Model(with_optimizer(GLPK.Optimizer)) cost = rand(clients, servers) # cost ...

Only top voted, non community-wiki answers of a minimum length are eligible