Skip to main content

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
17 votes
1 answer
358 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
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
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.5k
7 votes
2 answers
321 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.5k
7 votes
1 answer
872 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
4 votes
1 answer
410 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,377
4 votes
0 answers
251 views

Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
Qurious Cube's user avatar
3 votes
1 answer
90 views

Reformulating undirected to directed edges for MCF

As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges. By quoting them: The ...
Daniele Cuomo's user avatar
2 votes
1 answer
93 views

Is there a name for this problem?

Consider a graph $G = (V,E)$ where $V$ is the set of vertices and $E$ is the set of weighted edges. We want to create $N$ disjoint subsets of $V$ such that the sum of weights inside each subset is ...
BloodyOrange's user avatar
0 votes
1 answer
89 views

Coloring of nodes in a sensor networks

I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight. Higher the weight, stronger the interference between the ...
KGM's user avatar
  • 2,377