Questions tagged [graphs]
For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.
110
questions
24
votes
4
answers
1k
views
What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems
Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following:
Using off the shelf solvers
Optimality gap provability
...
- 1,069
17
votes
1
answer
362
views
Was there something specific that caused graph cuts to lose popularity in the last 5 years?
Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago:
For privacy I've cut the all ...
- 1,278
14
votes
3
answers
2k
views
A variant of the Multiple Traveling Salesman Problem
I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost.
Most of the ...
- 143
13
votes
5
answers
542
views
Connectivity of two nodes in an arbitrary undirected graph
Is there an efficient way to model the connectivity of two nodes in an arbitrary undirected graph? I would like to have a binary variable representing this connectivity: 1 if there exists a path ...
- 540
13
votes
1
answer
163
views
Re-calculating shortest path in slightly altered graph
I was wondering if someone has come across this before and/or has a smart idea for the following:
I have a directed graph $G$ with costs $c$ associated with the arcs, and I know the shortest path $P^...
11
votes
5
answers
2k
views
How to compute all paths between two given nodes in a network?
In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that:
no arc is used more than once
a given path does not contain more than $M$ arcs
...
- 13.7k
11
votes
2
answers
206
views
Neigbourhoods in Large Neighbourhood Search (LNS) algorithms
I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...
- 213
10
votes
3
answers
795
views
Graph problems as integer programs
Suppose I give a solver (CPLEX, Gurobi, SCIP or anything else) an IP which is a reformulation of a stable set problem (or vertex cover problem or coloring problem) of some graph, is there a way I can ...
10
votes
2
answers
422
views
Many-to-many Breadth First Search
There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a ...
- 912
10
votes
2
answers
592
views
How to maximize "contrast" between nodes on a graph?
I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
- 343
9
votes
1
answer
707
views
A variant of the Shortest Path Problem
Consider a layerwise directed acyclic graph DAG, $G=(V,E)$ and two vertices $s$ and $t$. $s$ is connected to all vertices in $L_0$, $L_0$ is connected to all vertices in $L_1$ and so forth. Consider ...
- 917
9
votes
2
answers
1k
views
Gurobi finishes with 'infeasible' although optimal solution exists
I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs.
I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
- 153
8
votes
3
answers
656
views
How to tackle this VRP variant?
I am currently working on the following problem, which is a variation of a vehicle routing problem. I am looking for different ideas to tackle it.
Problem description
A set of nodes with a given ...
- 13.7k
8
votes
1
answer
163
views
References for "metric" network flow problems
Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems.
Very efficient implementation of state-...
- 1,750
8
votes
1
answer
72
views
Covering problem on a network (?)
I have this problem described in natural language, and I was wondering whether it is relatable to any known problem.
I have a directed acyclic graph. Each node can host a "probe". If node $i$ hosts ...
- 937
8
votes
0
answers
119
views
Multiple shipments with FILO order
I am trying to solve a problem statement with the help of jsprit.
There is a depot.
Identical items need to be delivered or picked up. An item can have two states: Bad or good.
Bad items need to be ...
- 139
7
votes
2
answers
633
views
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms.
It can also be formulated as an integer linear program.
In ...
- 1,015
7
votes
1
answer
1k
views
How to use the least number of colors to color different routes of a bus route such that no two intersecting routes will have the same color?
I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colors to color the routes, ...
7
votes
3
answers
984
views
Combining Multiple Cost Values in Shortest Path Problem
I am trying to solve a shortest path problem through Dijkstra's algorithm. However in my case, cost between nodes (nodes $i$ and $j$) are more than one- two nodes are compared based on two different ...
- 179
7
votes
2
answers
3k
views
The general meaning of "constraint relaxation" in the context of the Shortest Path Problem
I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges")
[...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
- 169
7
votes
1
answer
890
views
Minimum vertex cover and linear programming
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...
7
votes
1
answer
191
views
Name of graph algorithm arising while using the Ryan Foster Branching
I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree.
Let's say ...
- 173
7
votes
2
answers
323
views
Traffic lights optimization
I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below:
The goal is maximize the duration during which each movement $m\in M=\{...
- 13.7k
7
votes
0
answers
113
views
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
- 13.7k
6
votes
2
answers
273
views
Heuristic solution to the graph partitioning problem
I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups?
But I need some MILP solver to solve ...
- 2,397
6
votes
2
answers
270
views
How to partition a giant tour into feasible routes?
In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then ...
- 13.7k
6
votes
1
answer
779
views
What is intended when we use "robustness", "resilience" and "reliability" in Operations Research?
I will use an example to detail my question but I would like you to keep in mind that I wanted to define:
Robustness,
Resillience,
Reliability
in the most general case within Operations Research.
...
- 819
6
votes
3
answers
2k
views
How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?
A simple algorithm may be traverse all vertices, and perform DFS for every vertex.
However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the ...
6
votes
1
answer
834
views
Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?
I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
- 447
6
votes
1
answer
94
views
Maximum weight b-matching with global cardinality constraint
Suppose $A$ is an $n$-by-$n$ symmetric matrix whose entries are all nonnegative. $A_{ii} = 0$ for all $i$. We want to find an $n$-by-$n$ binary ($0/1$ valued) matrix $X$ that maximizes
$$\sum_{ij} A_{...
- 61
6
votes
0
answers
95
views
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ ...
- 93
5
votes
4
answers
264
views
Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends
Consider a graph whose vertices can be partitioned into $n$ layers. Edges exist only between vertices in successive layers. So, there are edges between layers $1$ and $2$, between layers $2$ and $3$ ...
- 343
5
votes
2
answers
398
views
Shortest path problem with underlying continuous variables
I recently got interested in the following variation of the shortest path problem. I've looked in the literature for days but I couldn't find any paper studying this problem. I'd like to ask if you ...
- 275
5
votes
3
answers
391
views
Is this arc routing formulation correct?
Let $G=(V,E)$ be a graph. I would like to identify an eulerian cycle in $G$ with minimum cost, with an integer programing approach:
$x_{ij}$ are integer variables that denote the number of times that ...
- 51
5
votes
2
answers
183
views
Number of simple cycles on the graph
I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of ...
- 9,283
5
votes
1
answer
235
views
Additional resources for this type of problem formulation
I'm working on a problem with the following formulation:
\begin{align}
\min&\quad\sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij}
\\
\text{s.t.}&\quad \sum_j x_{ij} = 1 \quad \forall i \in N\\
&...
- 93
5
votes
1
answer
221
views
Flow problem with side constraints: how to eliminate subtours?
I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
- 13.7k
5
votes
1
answer
293
views
Quickest shortest path algorithm
I want to do a shortest path algorithm. My direct and not acyclic graph contains only positive numbers. I have to do the scan for all pairs of nodes in complete depth in python. My graph is big (...
- 659
5
votes
0
answers
207
views
Reduction from Steiner Tree to TSP
The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the ...
- 111
4
votes
3
answers
212
views
Is this ILP formulation for Group Closeness Centrality a column generation approach?
I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
4
votes
1
answer
426
views
How to partition a graph with optimal number of groups?
I have a graph with $N=12$ nodes. Some nodes may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is ...
- 2,397
4
votes
2
answers
160
views
Maximum Flow Problem : Can someone refer me to accessible valuable resources
Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
- 125
4
votes
2
answers
497
views
Any Solution for $k$-means with minimum and maximum cluster size constraint?
I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster.
$N$ be the number ...
- 2,397
4
votes
2
answers
769
views
MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?
I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019.
It's a problem about minimizing a sum of terms that are ...
- 1,278
4
votes
1
answer
63
views
What is the name of the graph where any edge is part of a cycle?
I wonder if there is a special category for this kind of graphs, I am thinking of a bidirectional graph but it would also be interesting in the cases when it is undirected.
I am thinking of something ...
- 95
4
votes
1
answer
255
views
Constrain Mixed-Integer problem such that a graph is fully connected
I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
- 4,049
4
votes
1
answer
109
views
Does anybody know the complexity of finding a maximum clique in circulant graphs?
I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
- 49
4
votes
1
answer
221
views
Efficiently updating latest finish times via Critical-Path-Method
For a Resource-Constrained-Project-Scheduling problem, I need to calculate Critical-Path-Method (CPM) values for each of the activities. These values are:
Earliest Start (ES)
Earliest Finish (EF)
...
- 115
4
votes
1
answer
147
views
Clustering a large ride-matching problem
Background: We are solving a large scale vehicle to person ride-matching problem. The problem is essentially simple (match every person with a vehicle, if possible), yet the problem size is quite ...
- 1,259
4
votes
1
answer
344
views
Creating constraints dynamically in pyomo abstract model
I have a networkX graph with few nodes and these nodes have attributes such as "demand".
...
- 69