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

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


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


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


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

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


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

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


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.


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

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

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

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


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