# Tag Info

## Hot answers tagged network-flow

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$, ...

7

Replace each undirected edge with two directed arcs in opposite directions. The original capacity constraint on each edge now applies to the sum of the arcs in both directions. If the costs are positive, every optimal solution will have flow in at most one of the two directions.

6

That IPOPT message means that IPOPT could not find a feasible solution to your problem. The reason could be either that: Once you set that value below 30, IPOPT can no longer find that basin of attraction (or that basin vanishes). Another feasible solution might exist (unless your problem is convex), but IPOPT can't find it. Your problem actually becomes ...

6

To be clear, you have a set $S$ of nodes of a graph $G=(V,A)$, with $S\subseteq V$, which must be visited. There is a special node $O$, which must be the starting point of a tour. A tour visiting the nodes in $S$ starting from $O$ (but not returning to $O$) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-...

6

Your intuition that you need to adjust $b_i$ is correct, but you also need to adjust $u_{i,j}$. To derive the desired MCF, perform a change of variables $y_{i,j}=x_{i,j}-\ell_{i,j}$ (so that the lower bound constraints become $y_{i,j} \ge 0$). That is, replace $x_{i,j}$ with $y_{i,j}+\ell_{i,j}$ throughout your constraints, and rewrite into the form of MCF....

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

5

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

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

5

Traditionally, the objective of the multicommodity flow problem is to minimize cost. The usual situation that the costs are positive naturally avoids cycles. The same idea arises with the shortest path problem: if the costs are positive, there are no negative cycles and an LP solver returns a path rather than a path plus cycles.

5

If the set $S$ of nodes to be visited is not too large, you can solve $|S|$ shortest path problems with additional constraints imposing a visit to some nodes. With your example, $|S|=|\{A,C \}|=2$ so it is not too bad. 1/ Find the shortest path from $O$ to $A$, while imposing a visit to node $C$. 2/ Then find the shortest path from $O$ to $C$, while ...

5

The general approach, whether you are using a mixed integer linear programming model or a constraint programming model, would be to have (nonnegative) variables representing the inventory of different materials at different times, plus flow constraints saying that the inventory at the end of each period is the starting inventory plus any production of the ...

4

"ON THE COMPLEXITY OF TIMETABLE AND MULTI-COMMODITY FLOW PROBLEMS" talks about integral flow while "Multicommodity flows over time: Efficient algorithms and complexity" does not. The integrality constraint (flows being integer valued) is important see LP vs ILP.

4

What you are looking for sounds like, combining the job-shop scheduling problem with material requirement planning or Multi-Periods Job-Shop Scheduling Problem. I am not aware how you would like to use that in the paper or real situation, but in the second one, applying mixed-integer programming (without boosting from the special algorithm like column ...

4

This sounds like a network optimization problem with inventory consideration. There could be two possible scenarios: You have already determined the location of potential warehouses. You'd like to determine potential locations in 1 - Do a greenfield analysis aka Centre-Of-Gravity https://www.anylogistix.com/solving-facility-location-problem-with-greenfield-...

4

The transformation you want is called node splitting. Replace node $i$ with two nodes $i'$ and $i''$, where all incoming arcs to node $i$ instead arrive at node $i'$ and all outgoing arcs from node $i$ instead leave node $i''$. Also introduce a directed arc from $i'$ to $i''$ with capacity $1$.

4

You can linearize by introducing a new binary variable $w_e^k$ to indicate whether edge $e$ appears in exactly one path for commodity $k$ and imposing the following constraints: \begin{align} \sum_{p\in P^k} \sigma_p^e (x_p^k - z_p^k) &\le w_e^k &&\text{for $e\in E$ and $k\in K$} \\ \sum_{p\in P^k} \sigma_p^e (z_p^k - x_p^k) &\le w_e^k &&...

4

If a flow somehow uses both $(u, v)$ and $(v, u)$, it is equivalent to another flow that only uses one of them. So if $f_{uv} \ge f_{vu} > 0$, treat it as the equivalent flow $\hat{f}$ where $\hat{f}_{a} = f_a$ for $a\notin\lbrace (u, v), (v, u) \rbrace$, $\hat{f}_{vu} = 0$ and $\hat{f}_{uv} = f_{uv} - f_{vu}$. I'm tempted to say that this will not happen ...

4

The "goods" going to or coming from the dummy node are not really moved; hence the cost of zero, no matter the quantity. If the problem is solved to optimality, using Network Simplex, or whatever, there is no "first" which can't be changed later as the algorithm proceeds. The algorithm ensures the total cost for moving everything is ...

3

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

3

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

3

you could try constraint programming / scheduling within CPLEX and use noOverlap to model the time matrix. In OPL that gives using CP; execute { cp.param.timelimit=10; } {string} nodes={"O","A","B","C","D","E","T"}; tuple edge { key string o; key string d; int time; } {edge} ...

3

I think your third constraint should be + 1, not - 1, on the right hand side. As stated, it says you enter destination nodes one time fewer than you exit them. You want to enter one time more. Fixing that will make the optimal solution feasible, but it will not make the model correct. There still remains the possibility of a solution that is not a contiguous ...

2

You can have a look at chapter 13, namely "Path and flow polyhedra and total unimodularity", of Alexander Schrijver's masterpiece "Combinatorial Optimization - Polyhedra and Efficiency". You will find characterizations based on cuts, which are the dual of flows in digraphs. This is linked to the famous max-flow min-cut theorem.

2

One approach is to introduce disaggregated variables $N_{ij}^{uv}$ where needed, in addition to the original $N_{ij}$ variables. For edges $(i,j)$ where merging requests is allowed, use your original capacity constraint. For edges $(i,j)$ where merging requests is not allowed, replace your original capacity constraint with \sum_{p\in P_{uv}\mid (i,j)\in p} ...

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

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

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

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.

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