本文介绍了一种增强学习方法，以更好地概括有关工作店调度问题（JSP）的启发式调度规则。 JSP上的当前模型并不关注概括，尽管正如我们在这项工作中所显示的那样，这是对问题进行更好的启发式方法的关键。改善概括的一种众所周知的技术是使用课程学习（CL）学习日益复杂的实例。但是，正如文献中许多作品所表明的那样，在不同问题大小之间传递学习技能时，这种技术可能会遭受灾难性的遗忘。为了解决这个问题，我们引入了一种新颖的对抗性课程学习（ACL）策略，该策略在学习过程中动态调整了难度级别以重新审视最坏情况的实例。这项工作还提出了一个深度学习模型来解决JSP，这是e var的W.R.T.作业定义和尺寸不可能。对Taillard和Demirkol的实例进行了实验，表明所提出的方法显着改善了JSP上的最新模型。它的平均最佳差距从Taillard的实例中的平均最佳差距从19.35 \％降低到10.46 \％，而Demirkol的实例中的平均最佳差距从38.43 \％降低到18.85％。我们的实施可在线提供。

组合优化问题在许多实际情况（例如物流和生产）中遇到，但是精确的解决方案尤其难以找到，通常对于大量的问题大小而言，通常是NP-HARD。为了计算近似解决方案，通常使用局部搜索的通用和特定问题的动物园。但是，哪种变体适用于哪种特定问题，即使对于专家来说也很难决定。在本文中，我们确定了这种本地搜索算法的三个独立算法方面，并将其在优化过程中正式选择为马尔可夫决策过程（MDP）。我们将深图神经网络设计为该MDP的策略模型，为当地搜索提供了一个名为Neurols的局部搜索控制器。充分的实验证据表明，神经元能够胜过操作研究和最新基于机器学习的方法的众所周知的通用本地搜索控制器。

组合优化的神经方法（CO）配备了一种学习机制，以发现解决复杂现实世界问题的强大启发式方法。尽管出现了能够在单一镜头中使用高质量解决方案的神经方法，但最先进的方法通常无法充分利用他们可用的解决时间。相比之下，手工制作的启发式方法可以很好地执行高效的搜索并利用给他们的计算时间，但包含启发式方法，这些启发式方法很难适应要解决的数据集。为了为神经CO方法提供强大的搜索程序，我们提出了模拟引导的光束搜索（SGB），该搜索（SGB）在固定宽度的树搜索中检查了候选解决方案，既是神经网络学习的政策又是模拟（推出）确定有希望的。我们将SGB与有效的主动搜索（EAS）进一步融合，其中SGB提高了EAS中反向传播的解决方案的质量，EAS提高了SGB中使用的策略的质量。我们评估了有关众所周知的CO基准的方法，并表明SGB可显着提高在合理的运行时假设下发现的解决方案的质量。

动态作业车间调度问题（DJSP）是一类是专门考虑固有的不确定性，如切换顺序要求和现实的智能制造的设置可能机器故障调度任务。因为传统方法不能动态生成环境的扰动面有效调度策略，我们制定DJSP马尔可夫决策过程（MDP）通过强化学习（RL）加以解决。为此，我们提出了一个灵活的混合架构，采用析取图的状态和一组通用的调度规则与之前最小的领域知识的行动空间。注意机制被用作状态的特征提取的图形表示学习（GRL）模块，并且采用双决斗深Q-网络与优先重放和嘈杂的网络（D3QPN）到每个状态映射到最适当的调度规则。此外，我们提出Gymjsp，基于众所周知的或图书馆公共标杆，提供了RL和DJSP研究社区标准化现成的现成工具。各种DJSP实例综合实验证实，我们提出的框架是优于基准算法可在所有情况下，较小的完工时间，并提供了在混合架构的各个组成部分的有效性实证理由。

This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.

事件处理是动态和响应互联网（物联网）的基石。该领域的最近方法基于代表性状态转移（REST）原则，其允许将事件处理任务放置在遵循相同原理的任何设备上。但是，任务应在边缘设备之间正确分布，以确保公平资源利用率和保证无缝执行。本文调查了深入学习的使用，以公平分配任务。提出了一种基于关注的神经网络模型，在不同场景下产生有效的负载平衡解决方案。所提出的模型基于变压器和指针网络架构，并通过Advantage演员批评批评学习算法训练。该模型旨在缩放到事件处理任务的数量和边缘设备的数量，不需要重新调整甚至再刷新。广泛的实验结果表明，拟议的模型在许多关键绩效指标中优于传统的启发式。通用设计和所获得的结果表明，所提出的模型可能适用于几个其他负载平衡问题变化，这使得该提案是由于其可扩展性和效率而在现实世界场景中使用的有吸引力的选择。

蒙特卡洛树搜索（MCT）是设计游戏机器人或解决顺序决策问题的强大方法。该方法依赖于平衡探索和开发的智能树搜索。MCT以模拟的形式进行随机抽样，并存储动作的统计数据，以在每个随后的迭代中做出更有教育的选择。然而，该方法已成为组合游戏的最新技术，但是，在更复杂的游戏（例如那些具有较高的分支因素或实时系列的游戏）以及各种实用领域（例如，运输，日程安排或安全性）有效的MCT应用程序通常需要其与问题有关的修改或与其他技术集成。这种特定领域的修改和混合方法是本调查的主要重点。最后一项主要的MCT调查已于2012年发布。自发布以来出现的贡献特别感兴趣。

最近的研究表明，神经组合优化（NCO）在许多组合优化问题（如路由）中具有优于传统算法的优点，但是对于涉及相互条件的动作空间的包装，诸如打包的更加复杂的优化任务的效率较低。在本文中，我们提出了一种经常性的条件查询学习（RCQL）方法来解决2D和3D包装问题。我们首先通过经常性编码器嵌入状态，然后采用先前操作的条件查询注意。条件查询机制填充了学习步骤之间的信息差距，将问题塑造为Markov决策过程。从复发中受益，单个RCQL模型能够处理不同尺寸的包装问题。实验结果表明，RCQL可以有效地学习用于离线和在线条带包装问题（SPP）的强烈启发式，优于空间利用率范围广泛的基线。 RCQL与最先进的方法相比，在离线2D 40盒案例中将平均箱间隙比率降低1.83％，3.84％。同时，我们的方法还实现了5.64％的空间利用率，对于1000件物品的空间利用率比现有技术更高。

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

钢筋学习最近在许多组合优化问题中显示了学习质量解决方案的承诺。特别地，基于注意的编码器 - 解码器模型在各种路由问题上显示出高效率，包括旅行推销员问题（TSP）。不幸的是，它们对具有无人机（TSP-D）的TSP表现不佳，需要在协调中路由车辆的异构队列 - 卡车和无人机。在TSP-D中，这两个车辆正在串联移动，并且可能需要在用于其他车辆的节点上等待加入。不那么关注的基于关注的解码器无法在车辆之间进行这种协调。我们提出了一种注意力编码器-LSTM解码器混合模型，其中解码器的隐藏状态可以代表所做的动作序列。我们经验证明，这种混合模型可提高基于纯粹的关注的模型，用于解决方案质量和计算效率。我们对MIN-MAX电容车辆路由问题（MMCVRP）的实验还确认混合模型更适合于多车辆的协调路由而不是基于注意的模型。

近年来，机器学习（ML）所证明的权力越来越吸引优化社区的兴趣，该界开始利用ML来增强和自动化最佳和近似算法的设计。 ML解决的一个组合优化问题是车间调度问题（JSP）。重点关注JSP和ML的大多数作品都是基于深入的强化学习（DRL），并且只有少数人利用监督的学习技术。避免有监督学习的反复出现的原因似乎是施放正确的学习任务的困难，即预测的有意义以及如何获得标签。因此，我们首先提出了一项新颖的监督学习任务，旨在预测机器排列的质量。然后，我们设计了一种原始方法来估算这种质量，以创建准确的顺序深度学习模型（二进制精度高于95％）。最后，我们通过凭经验证明了通过提高受文献作品启发的简单禁忌搜索算法的性能来预测机器排列质量的价值。

回溯搜索算法通常用于解决约束满足问题（CSP）。回溯搜索的效率在很大程度上取决于可变排序启发式。目前，最常用的启发式是根据专家知识进行手工制作的。在本文中，我们提出了一种基于深度的加强学习方法，可以自动发现新的变量订购启发式，更好地适用于给定类CSP实例。我们显示，直接优化搜索成本很难用于自动启动，并建议优化在搜索树中到达叶节点的预期成本。为了捕获变量和约束之间的复杂关系，我们设计基于图形神经网络的表示方案，可以处理具有不同大小和约束的CSP实例。随机CSP实例上的实验结果表明，学习的政策在最小化搜索树大小的方面优于古典手工制作的启发式，并且可以有效地推广到比训练中使用的实例。

最近，增强学习方法（RL）在NP-HARD组合优化问题上的应用已成为一个流行的话题。这本质上是由于传统组合算法的性质，通常是基于试验过程。 RL旨在自动化此过程。在这方面，本文着重于RL在车辆路由问题（VRP）中的应用，这是属于NP-HARD问题的著名组合问题。首先，在这项工作中，该问题被建模为马尔可夫决策过程（MDP），然后应用PPO方法（属于Actor-Critic-Critic cornforcion学习方法类别）。在第二阶段，已经建立了演员和评论家背后的神经建筑，选择采用基于卷积神经网络的神经建筑，包括演员和评论家。这种选择有效地解决了不同大小的问题。在各种实例上进行的实验表明该算法具有良好的概括能力，并且可以在短时间内达到良好的解决方案。提出的算法与最先进的求解器或最先进的求解器之间的比较表明，后者仍然优于强化学习算法。但是，有一些未来的研究观点，旨在升级提出的算法的当前性能。

深度强化学习（DRL）赋予了各种人工智能领域，包括模式识别，机器人技术，推荐系统和游戏。同样，图神经网络（GNN）也证明了它们在图形结构数据的监督学习方面的出色表现。最近，GNN与DRL用于图形结构环境的融合引起了很多关注。本文对这些混合动力作品进行了全面评论。这些作品可以分为两类：（1）算法增强，其中DRL和GNN相互补充以获得更好的实用性； （2）特定于应用程序的增强，其中DRL和GNN相互支持。这种融合有效地解决了工程和生命科学方面的各种复杂问题。基于审查，我们进一步分析了融合这两个领域的适用性和好处，尤其是在提高通用性和降低计算复杂性方面。最后，集成DRL和GNN的关键挑战以及潜在的未来研究方向被突出显示，这将引起更广泛的机器学习社区的关注。

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

In recent years, methods based on deep neural networks, and especially Neural Improvement (NI) models, have led to a revolution in the field of combinatorial optimization. Given an instance of a graph-based problem and a candidate solution, they are able to propose a modification rule that improves its quality. However, existing NI approaches only consider node features and node-wise positional encodings to extract the instance and solution information, respectively. Thus, they are not suitable for problems where the essential information is encoded in the edges. In this paper, we present a NI model to solve graph-based problems where the information is stored either in the nodes, in the edges, or in both of them. We incorporate the NI model as a building block of hill-climbing-based algorithms to efficiently guide the election of neighborhood operations considering the solution at that iteration. Conducted experiments show that the model is able to recommend neighborhood operations that are in the $99^{th}$ percentile for the Preference Ranking Problem. Moreover, when incorporated to hill-climbing algorithms, such as Iterated or Multi-start Local Search, the NI model systematically outperforms the conventional versions. Finally, we demonstrate the flexibility of the model by extending the application to two well-known problems: the Traveling Salesman Problem and the Graph Partitioning Problem.

广泛研究和使用旅行推销员问题等图形问题，如旅行推销员问题，或发现最小的施泰纳树在数据工程和计算机科学中使用。通常，在现实世界应用中，图表的特征往往会随着时间的推移而变化，因此，找到问题的解决方案变得具有挑战性。许多图表问题的动态版本是运输，电信和社交网络中普遍世界问题的关键。近年来，利用深度学习技术来寻找NP-Hard图组合问题的启发式解决方案，因为这些学习的启发式可以有效地找到近最佳解决方案。但是，大多数现有的学习启发式方法都关注静态图问题。动态性质使NP-Hard图表问题更具挑战性，并且现有方法无法找到合理的解决方案。在本文中，我们提出了一种名为Cabl时间关注的新型建筑，并利用加固学习（GTA-RL）来学习基于图形的动态组合优化问题的启发式解决方案。 GTA-RL架构包括能够嵌入组合问题实例的时间特征的编码器和能够动态地关注嵌入功能的解码器，以找到给定组合问题实例的解决方案。然后，我们将架构扩展到学习HeuRistics的组合优化问题的实时版本，其中问题的所有输入特征是未知的，而是实时学习。我们针对几种最先进的基于学习的算法和最佳求解器的实验结果表明，我们的方法在动态和效率方面，在有效性和最佳求解器方面优于基于最先进的学习方法。实时图组合优化。

我们提出了一个通用图形神经网络体系结构，可以作为任何约束满意度问题（CSP）作为末端2端搜索启发式训练。我们的体系结构可以通过政策梯度下降进行无监督的培训，以纯粹的数据驱动方式为任何CSP生成问题的特定启发式方法。该方法基于CSP的新型图表，既是通用又紧凑的，并且使我们能够使用一个GNN处理所有可能的CSP实例，而不管有限的Arity，关系或域大小。与以前的基于RL的方法不同，我们在全局搜索动作空间上运行，并允许我们的GNN在随机搜索的每个步骤中修改任何数量的变量。这使我们的方法能够正确利用GNN的固有并行性。我们进行了彻底的经验评估，从随机数据（包括图形着色，Maxcut，3-SAT和Max-K-Sat）中学习启发式和重要的CSP。我们的方法表现优于先验的神经组合优化的方法。它可以在测试实例上与常规搜索启发式竞争，甚至可以改善几个数量级，结构上比训练中看到的数量级更为复杂。

Coflow是最近提出的网络抽象，以帮助提高数据并行计算作业的通信性能。在多阶段作业中，每个作业包括多个Coflows，由定向的非循环图（DAG）表示。有效地调度Coflows对于提高数据中心中的数据并行计算性能至关重要。与手动调度启发式相比，现有的工作Deepweave [1]利用强化学习（RL）框架自动生成高效的CoFlow调度策略。它采用图形神经网络（GNN）来编码一组嵌入向量中的作业信息，并将包含整个作业信息的平面嵌入载体馈送到策略网络。然而，这种方法的可扩展性差，因为它无法应对由任意尺寸和形状的DAG表示的作业，这需要大型策略网络来处理难以训练的高维嵌入载体。在本文中，我们首先利用了一条定向的无循环图神经网络（DAGNN）来处理输入并提出一种新型流水线-DAGNN，其可以有效地加速DAGNN的特征提取过程。接下来，我们馈送由可调度的Coflows组成的嵌入序列，而不是将所有Coflows的平面嵌入到策略网络上，并输出优先级序列，这使得策略网络的大小仅取决于特征的维度而不是产品的维度作业的DAG中的节点数量和节点数量，提高优先级调度策略的准确性，我们将自我注意机制纳入深度RL模型，以捕获嵌入序列不同部分之间的交互，以使输出优先级进行输出优先级分数相关。基于此模型，我们开发了一种用于在线多级作业的Coflow调度算法。

为混合整数线性编程问题（MILLS）找到高质量解决方案对于许多实际应用非常重要。在这方面，提出了精炼启发式局部分支（LB）来生产改进解决方案，并且对MILP中的本地搜索方法的开发产生了高度影响力。该算法迭代地探索由所谓的本地分支约束定义的一系列解决方案邻域，即，限制与参考解决方案的距离的线性不等式。对于LB算法，邻域大小的选择对于性能至关重要。虽然它是由原始LB方案中的保守值初始化的，但我们的新观察是最佳规模强烈依赖于特定的MILP实例。在这项工作中，我们调查搜索附近的大小与底层LB算法的行为之间的关系，我们设计了一种基于倾斜的框架，用于引导LB启发式的邻居搜索。该框架由两阶段战略组成。对于第一阶段，训练缩放的回归模型以通过回归任务在第一迭代中预测LB邻域的大小。在第二阶段，我们利用加强学习和设计加强的邻域搜索策略，以动态调整随后的迭代处的大小。我们计算地表明，确实可以学习邻域大小，导致改进的性能，并且整个算法在实例大小相对于实例大小概括，并且显着地跨越实例概括。