# 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,929
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, ...
• 33.2k

### 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 ...
• 13.6k

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

### Fast algorithm for Transportation Problem in Python?

You could try to solve it as a min cost flow problem. NetworkX is a package for graph algorithms and has algorithms for this implemented. It can easily be installed via ...
• 3,655
Accepted

• 8,677

### How to visit a subset of network nodes in a single trip?

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 ...
• 13.6k

### How to include material flow in job shop scheduling problem (as constraint?)?

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

### Is Multicommodity Flow problem really NP-hard?

"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. ...
• 4,037
Accepted

Your conjecture is wrong as the following counterexample demonstrates. Consider $$A = \begin{pmatrix} 1 & 0 & -1 \\ 1 & 1 & 0 \end{pmatrix}$$ and $$b^\top = \begin{pmatrix} -1 & ... • 1,572 4 votes ### Max flow problem without splitting the flow from the supply nodes - LP formulation help 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:$$...
• 8,677
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}