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 ...
- 5,909
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, ...
- 30.5k
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 ...
- 12.9k
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.
...
- 91
9
votes
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,635
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 $...
- 30.5k
7
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 ...
- 30.5k
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 ...
- 11.9k
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 ...
- 30.5k
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 ...
- 37.9k
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 ...
- 12.9k
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 ...
- 671
6
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 ...
- 30.5k
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 ...
- 2,316
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 ...
- 6,352
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\...
- 30.5k
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 ...
- 30.5k
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 ...
- 30.5k
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 ...
- 30.5k
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 ...
- 37.9k
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 ...
- 30.5k
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.
- 30.5k
5
votes
Accepted
Combined arc capacity constraints in network flows
These are called Generalized Upper Bound (GUB) constraints.
- 30.5k
5
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 $...
- 8,622
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 ...
- 12.9k
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 ...
- 37.9k
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,622
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}
- 12.9k
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 ...
- 5,342
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 ...
- 2,401
Only top scored, non community-wiki answers of a minimum length are eligible