Questions tagged [graphs]

For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.

Filter by
Sorted by
Tagged with
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 ...
fhk's user avatar
  • 1,069
17 votes
1 answer
344 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 ...
Nike Dattani's user avatar
  • 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 ...
kemalduldul's user avatar
13 votes
5 answers
511 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 ...
Mertcan Yetkin's user avatar
13 votes
1 answer
159 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^...
Martim Joyce-Moniz's user avatar
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 ...
Kuifje's user avatar
  • 13.2k
11 votes
2 answers
197 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 ...
GGJON's user avatar
  • 213
10 votes
3 answers
785 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 ...
Sriram Sankaranarayanan's user avatar
10 votes
2 answers
420 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 ...
Evren Guney's user avatar
10 votes
2 answers
567 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 "...
Ike348's user avatar
  • 283
9 votes
1 answer
698 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 ...
ephemeral's user avatar
  • 897
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 ...
Legsleg's user avatar
  • 153
8 votes
3 answers
611 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 ...
Kuifje's user avatar
  • 13.2k
8 votes
1 answer
160 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-...
Stefano Gualandi's user avatar
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 ...
Libra's user avatar
  • 937
8 votes
0 answers
116 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 ...
Aman Kumar's user avatar
7 votes
2 answers
616 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 ...
Erel Segal-Halevi's user avatar
7 votes
1 answer
1k views

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

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 colours to colour the routes, ...
Burhanuddin Samiwala's user avatar
7 votes
3 answers
827 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 ...
Monotros's user avatar
  • 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 ...
Alexey's user avatar
  • 169
7 votes
1 answer
841 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}...
Mario Giambarioli's user avatar
7 votes
2 answers
318 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=\{...
Kuifje's user avatar
  • 13.2k
7 votes
1 answer
167 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 ...
Victor Hugo's user avatar
7 votes
0 answers
101 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 ...
Kuifje's user avatar
  • 13.2k
6 votes
2 answers
269 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 ...
KGM's user avatar
  • 2,211
6 votes
2 answers
255 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 ...
Kuifje's user avatar
  • 13.2k
6 votes
1 answer
725 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. ...
JKHA's user avatar
  • 679
6 votes
3 answers
1k 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 ...
LighTofHeaveN's user avatar
6 votes
1 answer
744 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 ...
Jacob Myer's user avatar
6 votes
1 answer
93 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_{...
user306101's user avatar
6 votes
0 answers
91 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)$ ...
Jin Kazama's user avatar
5 votes
4 answers
257 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$ ...
Rohit Pandey's user avatar
5 votes
2 answers
341 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 ...
Tobia Marcucci's user avatar
5 votes
3 answers
387 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 ...
husson's user avatar
  • 51
5 votes
2 answers
139 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 ...
A.Omidi's user avatar
  • 8,717
5 votes
1 answer
232 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\\ &...
Bob Jeans's user avatar
5 votes
1 answer
196 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 ...
Kuifje's user avatar
  • 13.2k
5 votes
1 answer
235 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 (...
maxmitz's user avatar
  • 659
5 votes
0 answers
194 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 ...
user12632521's user avatar
4 votes
3 answers
205 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 ...
Christian Komusiewicz's user avatar
4 votes
1 answer
384 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 ...
KGM's user avatar
  • 2,211
4 votes
2 answers
158 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.
JirenOppaik's user avatar
4 votes
2 answers
423 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 ...
KGM's user avatar
  • 2,211
4 votes
2 answers
638 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 ...
Nike Dattani's user avatar
  • 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 ...
jeroaranda's user avatar
4 votes
1 answer
212 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 ...
worldsmithhelper's user avatar
4 votes
1 answer
95 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?
Fabio Furini's user avatar
4 votes
1 answer
206 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) ...
Rutger's user avatar
  • 115
4 votes
1 answer
143 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 ...
tcokyasar's user avatar
  • 1,249
4 votes
1 answer
288 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
Waqas Swati's user avatar