文件名称：用于表示、比较和分类整数程序的基于图的方法-研究论文
文件大小：12.45MB
文件格式：PDF
更新时间：2024-06-30 03:25:39
graph convolutional network
长期以来，人们一直观察到模型结构可能在确定某些求解技术对混合整数线性规划 (MILP) 的有效性方面发挥重要作用。 一个含义是，对一类 MILP 工作良好的求解技术通常被发现对其他“类似”问题也有效。 尽管有潜在的好处，但在识别 MILP 之间的相似性领域的研究有限。 本文试图通过基于数学结构对 MILP 实例进行分类和比较的框架来解决这一差距。 提出了一种新的基于图形的 MILP 表示，其中决策变量和约束由节点描述，弧表示某些约束中决策变量的存在。 受图结构数据深度学习领域最新进展的启发，提供了两种利用 MILP 图表示进行分类和比较的方法。 在第一种关系方法中，使用图卷积网络 (GCN) 将这些所谓的 MILP 图分类为来自已知数量的问题类型之一。 第二种方法利用 GCN 学习的潜在特征来直接比较图。 作为后一种方法的一部分，我们引入了基于图的结构相似性的正式度量。 实证研究表明，分类和比较程序在测试集上都表现良好。 还通过一系列案例研究探讨了 MILP 图的其他属性。