Tag Info

Hot answers tagged graphs

Accepted

What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

As far as I understand it, all machine learning approaches used for solving (combinatorial) optimization problems, and in particular reinforcement learning, work as follows: Use a greedy algorithm to ...
• 5,869

What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

Reinforcement learning is set of the algorithms which are used to solve Markov Decision Processes and its variants, e.g. Partially Observed MDP (POMDP). Most of the problems that we deal with them ...
Accepted

A variant of the Shortest Path Problem

Wouldn't eliminating all outgoing arcs from the red node except to the blue node, and eliminating all arcs from the green node except to the yellow node, or in general, eliminating all arcs from $a$ ...
• 5,869

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

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a ...
• 543
Accepted

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for ...
• 1,859
Accepted

How to partition a graph with optimal number of groups?

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ ...
• 27.1k

Connectivity of two nodes in an arbitrary undirected graph

From the question and the comments I gather that you really only have one pair between with connectivity could be established (by activating edges) and whether this is the case or not should be ...
• 5,869

Graph problems as integer programs

CPLEX has a parameter (RootAlgorithm) that lets you select the method for solving an LP (or for solving the root node relaxation of an ILP). The default setting is to let CPLEX choose, which usually (...
• 35.5k
Accepted

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/...

Graph problems as integer programs

Often such problems have side constraints, and this patent covers that more general case, using Dantzig-Wolfe decomposition with the network subproblem (MST, TSP, etc.) expressed compactly (not ...
• 27.1k

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. ...

A variant of the Multiple Traveling Salesman Problem

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting. Defining ...
• 5,982
Accepted

A variant of the Multiple Traveling Salesman Problem

Y. Kaempfer and L. Wolf, in their recent paper [1] applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be ...
• 8,453
Accepted

Re-calculating shortest path in slightly altered graph

In DP Bertsekas Network Optimization (that can be downloaded for free) there's an exercise at Page 104 (Finding an initial price vector) where you can find a method for solving shortest paths in ...
• 1,519

Many-to-many Breadth First Search

Since your graph is directed you can first compute the strongly connected components in linear time $O(n+m)$, contract the components, and then run BFS on the contracted graph. For each strongly ...
• 2,705

What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

A main reason to use Reinforced Learning (RL) is because you don't know the dynamics (update rules) of the system. If you don't know the details of how the system will update, you will not be able to ...
• 512

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

These common neighborhoods for TSP/VRP might be useful: 2-opt, 3-opt, ..., k-opt change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain swap 2 visits change a subchain of ...
• 4,645
Accepted

What is the name of the graph where any edge is part of a cycle?

Such a graph is called bridgeless.
• 27.1k
Accepted

What is intended when we use "robustness", "resilience" and "reliability" in Operations Research?

I think these terms are all rather vague and imprecise, and different people use them slightly differently. Some papers try to draw clear lines between them—for example, in my dissertation in 2003, I ...
• 12.9k

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum ...
• 3,115

How to compute all paths between two given nodes in a network?

I would solve this using the following approach: Compute the shortest path with a MIP, with an additional constraint to limit the number of arcs in the path. If a path is found, store it, add a no ...
• 11.8k

Is there any way to generate all the possible undirected graphs with unlabeled nodes?

See http://oeis.org/A000088, which gives a different number (34) for n = 5.
• 27.1k
Accepted

Graph problems as integer programs

I suspect there are a few specific problems for which the answer is "yes," and I hope others will answer to provide examples of those. But in general I believe the answer is "no." For example, if you ...
• 12.9k