12 votes

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 ...
user avatar
10 votes
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, ...
user avatar
  • 22.7k
9 votes

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. ...
user avatar
9 votes

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 ...
user avatar
  • 10.4k
9 votes
Accepted

How to Model Path Being Only Through Adjacent Cells

A standard approach for modeling a path from source $s$ to sink $t$ in a directed graph with node set $N$ and arc set $A$ is to let continuous variable $x_{ij} \ge 0$ represent the flow along the arc $...
user avatar
  • 22.7k
7 votes
Accepted

pyomo/ipopt: nonlinear network optimization not converging

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 ...
user avatar
7 votes

(Integral) multi-commodity flow on undirected graph

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 ...
user avatar
  • 22.7k
7 votes

Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution

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 ...
user avatar
  • 30.8k
6 votes
Accepted

Maximum Flow Problem : Can someone refer me to accessible valuable resources

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 ...
user avatar
  • 10.4k
6 votes

What is the impact of making flow fractional rather than integer?

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 ...
user avatar
6 votes
Accepted

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

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 ...
user avatar
  • 5,445
6 votes
Accepted

Min Cost Flow with lower bound reduction to MCF algorithm

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 ...
user avatar
  • 22.7k
6 votes
Accepted

Extreme point and extreme ray of a network flow problem

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 ...
user avatar
6 votes
Accepted

Problems modeling a constraint in network design problem

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\...
user avatar
  • 22.7k
6 votes
Accepted

Does multi-commodity flow problem (MCF) block cycling flows?

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 ...
user avatar
  • 22.7k
6 votes

Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution

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 ...
user avatar
  • 22.7k
6 votes
Accepted

Model the TSP as a shortest path

One approach is to create a node $(S,u)$ for each subset $S\subseteq N$ and last-visited city $u\in N$. The main arcs are from $(S,u)$ to $(S\cup\{v\},v)$, with cost $d_{u,v}$. You also need an arc ...
user avatar
  • 22.7k
5 votes
Accepted

Adding slack nodes to min cost network flows

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 ...
user avatar
  • 30.8k
5 votes
Accepted

Solving general minimum cost flow problems using only one demand and one supply node

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 ...
user avatar
  • 22.7k
5 votes
Accepted

How can I find the shortest path for all nodes in a graph from a source $s$?

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 ...
user avatar
  • 22.7k
5 votes

Algorithm / Method for determining N nodes to disconnect group of nodes

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.
user avatar
  • 22.7k
5 votes
Accepted

Combined arc capacity constraints in network flows

These are called Generalized Upper Bound (GUB) constraints.
user avatar
  • 22.7k
5 votes

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 ...
user avatar
  • 10.4k
5 votes

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 ...
user avatar
  • 30.8k
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: $$...
user avatar
  • 8,330
4 votes

Max flow problem without splitting the flow from the supply nodes - LP formulation help

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}
user avatar
  • 10.4k
4 votes

Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

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 $...
user avatar
  • 8,330
4 votes
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 ...
user avatar
  • 5,192
4 votes
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 ...
user avatar
  • 2,385
4 votes
Accepted

Min-cost flow with per-edge flow conservation

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 ...
user avatar
  • 2,689

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