Hot answers tagged

26 votes
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 ...
Marco Lübbecke's user avatar
15 votes

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 ...
Afshin Oroojlooy's user avatar
14 votes
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$ ...
Marco Lübbecke's user avatar
14 votes

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 ...
Richard's user avatar
  • 543
11 votes
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 ...
Albert Schrotenboer's user avatar
11 votes
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)$ ...
RobPratt's user avatar
  • 30.4k
10 votes

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 ...
Marco Lübbecke's user avatar
10 votes

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 (...
prubin's user avatar
  • 37.8k
10 votes
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/...
Matthew Galati's user avatar
9 votes

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 ...
RobPratt's user avatar
  • 30.4k
9 votes

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. ...
Paul Swoboda's user avatar
9 votes

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 ...
Kevin Dalmeijer's user avatar
9 votes
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 ...
Oguz Toragay's user avatar
  • 8,622
8 votes
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 ...
Claudio Contardo's user avatar
8 votes

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 ...
Marcus Ritt's user avatar
  • 2,705
8 votes

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 ...
Qian Zhang's user avatar
8 votes

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 ...
Geoffrey De Smet's user avatar
8 votes
Accepted

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

Such a graph is called bridgeless.
RobPratt's user avatar
  • 30.4k
8 votes
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 ...
LarrySnyder610's user avatar
8 votes

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 ...
Joris Kinable's user avatar
8 votes

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 ...
Kuifje's user avatar
  • 12.9k
7 votes

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.
RobPratt's user avatar
  • 30.4k
7 votes
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 ...
LarrySnyder610's user avatar
7 votes
Accepted

Heuristic solution to the graph partitioning problem

A greedy heuristic is natural to try here: Declare all groups to be admissible. Find an admissible group $g$ with the largest weight. Set $u_g=1$. Declare all groups $h$ with $N_h \cap N_g \not= \...
RobPratt's user avatar
  • 30.4k
7 votes

How to tackle this VRP variant?

This is a Two-Echelon Vehicle Routing Problem. Here is a recent review of the literature on this problem: "Two-Echelon Vehicle Routing Problems: A Literature Review" (Sluijk et al., 2022) ...
fontanf's user avatar
  • 2,495
7 votes
Accepted

Is this ILP formulation for Group Closeness Centrality a column generation approach?

I would not call the approach column generation. That term is usually applied to methods where columns are constructed using information from the solution of a previous version of the problem. What ...
prubin's user avatar
  • 37.8k
6 votes
Accepted

Maximum Flow Problem : Can someone refer me to accessible valuable resources

Here is one suggestion : Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, Orli. The maximum flow problem is delt with in chapters 6-8, but I suggest you read the ones before if ...
Kuifje's user avatar
  • 12.9k
6 votes

How to maximize "contrast" between nodes on a graph?

If you are dealing with Voronoi diagrams then perhaps your graph is planar, and in this case there is probably a good heuristic for the problem, but more details should be given I think before going ...
Kuifje's user avatar
  • 12.9k
6 votes
Accepted

How to maximize "contrast" between nodes on a graph?

You can solve this as a quadratic assignment problem. With the same $x$ variables as in @Kuifje's answer, you want to maximize $$\sum_{(u,v)\in A}\sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| ...
RobPratt's user avatar
  • 30.4k
6 votes

Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends

I don't know whether this will be efficient enough for your real graph sizes, but with binary decision variables $x_{v,k}$ to indicate whether vertex $v$ is assigned label $k$, you can obtain a ...
RobPratt's user avatar
  • 30.4k

Only top scored, non community-wiki answers of a minimum length are eligible