Post #46

Combinatorial Optimization + ML How can you solve traveling salesman problem (TSP) with ML? One way is to train the agent to make decisions about the next step. This requires that you either imitate already existing solutions or obtain the reward and then update the policy. This works if you have a solver to the problem which can generate solutions or if the problem is easy enough to converge to optimal value fast (e.g. Euclidean TSP). For harder problems, you can integrate ML inside the solver (which has exponential runtime in the worst-case). So your solver still guarantees the optimality of the solutions but heuristic choices, which exist in most solvers, are done by ML. This is what Exact Combinatorial Optimization with Graph Convolutional Neural Networks (https://arxiv.org/abs/1906.01629) proposes for Branch & Bound procedure, which heuristically chooses the next node for branching. Results are quite impressive, showing that you can decrease the running time of SOTA solvers while preserving optimality, even if the branching choice of ML model does not have guarantees.