Questions tagged [graphs]
For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.
121 questions
3
votes
2
answers
201
views
Finding multiple non-crossing optimal paths across a weighted grid with minimum vertical spacing
I’m working on an optimization problem that I believe can be framed as a graph or flow problem, but I haven’t found a good existing formulation that scales efficiently. I’d like advice on how to model ...
- 133
0
votes
0
answers
75
views
How can I formulate this disaggregation problem as a network flow?
I am struggling to formulate this disaggregation problem as a network flow. Can anyone help me see a way to make things work? I am not fully familiar with all of the tricks and gadgets for network ...
- 1
1
vote
0
answers
69
views
How to give a sufficient or necessary condition of a ILP's relaxation?
I have a class of ILP questions in the form of:
\begin{align*}
\text{Max} \quad & c^T x \\
\text{subject to} \quad & Ax \leq b \\
& A \in \{0,-1,1\}^{(m+n+mn)*(mn+n)...
- 11
5
votes
1
answer
272
views
MIP model for minimum spanning tree
In this post, Erwin Kalvelagen explores how the minimum spanning tree problem can me modeled with different MIPs. The models are based on Optimal Trees (Magnanti, Wolsey).
In the flow formulation II, ...
- 488
2
votes
0
answers
63
views
Graph crossing minimization problem
I would like to formulate the graph crossing minimization problem as a MI(N)LP (it's ok if it is non linear) : given a graph $G(V,E)$, what is the minimum number of edge crossings in any drawing of $G$...
- 488
5
votes
1
answer
1k
views
Does Dijkstra's Algorithm Correspond to a Specially Structured Integer Programming Formulation?
Dijkstra's algorithm efficiently solves the shortest path problem for graphs very well. I suspect that this efficiency might imply the existence of a specially structured integer programming (IP) ...
0
votes
1
answer
182
views
Use Gurobi to create networkx.Graph that has highest max flow
I have a networkx.Graph-object called G.
...
- 13
1
vote
0
answers
86
views
Finding the Maximum Weight Perfect Bipartite Matching starting from a Perfect Bipartite Matching
Given a sparse weighted bipartite graph, weights are reals between [0, 1]. I have to find in quick succession a Perfect Matching (any weight), followed by the Maximum Weight Perfect Matching.
I obtain ...
- 11
3
votes
1
answer
250
views
Minimizing the number of non-zero flows
Let $G$ be a directed graph, and let $b : V (G) \to \mathbb{R}$ be a supply/demand function such that $\sum_{v \in V (G)} b(v) = 0$. Let $\delta^+ (v)$ and $\delta^- (v)$ denote the sets of outgoing ...
3
votes
1
answer
237
views
Time-space networks: References to understand the framework and related tips/tricks
Time-space representation is one of the effective tools for modeling problems in logistics/transportation. I am doing a session for OR practitioners where I plan to go deep into examples and tips/...
- 157
1
vote
0
answers
56
views
Partition edges of a graph by paths where each path can only consist of edges sharing the same property
Say I have an undirected graph where each edge is tagged with a list of properties, e.g. one edge may satisfy property A and B, and another only B and C, etc.
The goal is to partition the edges of the ...
- 53
4
votes
2
answers
272
views
Improving MILP formulation (profitability based network design)
I have to design a network based on a profitability criteria, however I encounter some practical problems in the solving phase.
Formulation of the problem
We have a graph $G=(V, E)$, with subset $P$ ...
- 43
2
votes
1
answer
73
views
updating cliques for an updated graph
A graph $G$ has nodes $V$ and edges $E$. Let's say I have found the maximum clique or all the cliques in $G$ with any algorithm, such as the Bron-Kerbosch algorithm. After a while, $E$ has been ...
- 613
3
votes
2
answers
247
views
Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs
I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
- 61
1
vote
0
answers
103
views
Complexity of cardinality constrained maximum weight independent set problem
Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
- 2,154