# Tag Info

### How do we call this problem in literature and how to model it?

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 ...
• 5,809
Accepted

### How to describe the traveling salesman problem with an integer programming model?

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, ...
• 22.7k

### Was there something specific that caused graph cuts to lose popularity in the last 5 years?

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

### How to solve this convex problem heuristically?

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 ...
• 10.4k
Accepted

• 8,330
Accepted

### References for "metric" network flow problems

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 ...
• 5,192
Accepted

### Complexity \ Reference request for variant of max flow problem

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 ...
• 2,385