# Tag Info

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$, ... 7 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. ... 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. 7 I don't know any references, but I can suggest a possible approach. For each commodity, generate a set of possible paths from the source of the commodity to the sink of the commodity. Let$x_a$be the flow of that commodity on arc$a$in your solution (I'm skipping commodity indices since we'll do each commodity separately) and let$H$be a matrix with$H_{a,...

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

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

6

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

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

You can generate such a flow decomposition dynamically by treating each arc flow as an arc capacity and solving a maximum capacity s-t path problem to find a path. Then reduce the arc capacities along this path by the maximum flow value. Repeat until all arc capacities are $0$. For a more general approach when you do not have a specified source and sink, ...

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

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 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. 5 These are called Generalized Upper Bound (GUB) constraints. 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 ... 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. 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

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

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

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

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