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 ...
- 5,909
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 ...
- 825
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$ ...
- 5,909
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 ...
- 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 ...
- 1,859
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)$ ...
- 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 ...
- 5,909
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 (...
- 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/...
- 516
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 ...
- 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.
...
- 91
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 ...
- 6,063
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 ...
- 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 ...
- 1,549
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 ...
- 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 ...
- 512
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 ...
- 4,717
8
votes
Accepted
What is the name of the graph where any edge is part of a cycle?
Such a graph is called bridgeless.
- 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 ...
- 13.1k
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 ...
- 3,396
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 ...
- 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.
- 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 ...
- 13.1k
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= \...
- 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) ...
- 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 ...
- 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 ...
- 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 ...
- 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| ...
- 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 ...
- 30.4k
Only top scored, non community-wiki answers of a minimum length are eligible