Machine learning pipelines that include a combinatorial optimization layer can give surprisingly efficient heuristics for difficult combinatorial optimization problems. Three questions remain open: which architecture should be used, how should the parameters of the machine learning model be learned, and what performance guarantees can we expect from the resulting algorithms? Following the intuitions of geometric deep learning, we explain why equivariant layers should be used when designing such pipelines, and illustrate how to build such layers on routing, scheduling, and network design applications. We introduce a learning approach that enables to learn such pipelines when the training set contains only instances of the difficult optimization problem and not their optimal solutions, and show its numerical performance on our three applications. Finally, using tools from statistical learning theory, we prove a theorem showing the convergence speed of the estimator. As a corollary, we obtain that, if an approximation algorithm can be encoded by the pipeline for some parametrization, then the learned pipeline will retain the approximation ratio guarantee. On our network design problem, our machine learning pipeline has the approximation ratio guarantee of the best approximation algorithm known and the numerical efficiency of the best heuristic.
翻译:包括组合优化层的机器学习管道能够给难以组合优化的问题带来令人惊讶的高效循环。 有三个问题仍然有待解决: 哪些结构应该使用, 机器学习模型的参数应该如何学习, 以及我们从由此产生的算法中可以期待什么性能保障? 在几何深学习的直觉之后, 我们解释为什么在设计这种管道时应该使用等离异层, 并演示如何在路线、 时间安排和网络设计应用程序上建立这种层。 我们引入了一种学习方法, 使得在培训组只包含困难优化问题而不是最佳解决方案的例子时能够学习这种管道, 并在我们的三个应用程序上展示其数字性能。 最后, 我们用统计学习理论的工具证明我们是一个标本, 展示了估算器的趋同速度 。 作为必然的结果, 我们得到的是, 如果一个近比算法可以通过管道为某种平衡化而编码, 那么所学的管道将保留近似比率保证。 关于我们的网络设计问题, 我们的机器学习管道有最接近比率保证已知的最佳精确算法和最佳黑理论的数字效率。