Feasible solutions are crucial for Integer Programming (IP) since they can
substantially speed up the solving process. In many applications, similar IP
instances often exhibit similar structures and shared solution distributions,
which can be potentially modeled by deep learning methods. Unfortunately,
existing deep-learning-based algorithms, such as Neural Diving and
Predict-and-search framework, are limited to generating only partial feasible
solutions, and they must rely on solvers like SCIP and Gurobi to complete the
solutions for a given IP problem. In this paper, we propose a novel framework
that generates complete feasible solutions end-to-end. Our framework leverages
contrastive learning to characterize the relationship between IP instances and
solutions, and learns latent embeddings for both IP instances and their
solutions. Further, the framework employs diffusion models to learn the
distribution of solution embeddings conditioned on IP representations, with a
dedicated guided sampling strategy that accounts for both constraints and
objectives. We empirically evaluate our framework on four typical datasets of
IP problems, and show that it effectively generates complete feasible solutions
with a high probability (> 89.7 \%) without the reliance of Solvers and the
quality of solutions is comparable to the best heuristic solutions from Gurobi.
Furthermore, by integrating our method's sampled partial solutions with the
CompleteSol heuristic from SCIP, the resulting feasible solutions outperform
those from state-of-the-art methods across all datasets, exhibiting a 3.7 to
33.7\% improvement in the gap to optimal values, and maintaining a feasible
ratio of over 99.7\% for all datasets.

我们提出了一种新颖的框架，通过对整数规划实例和解决方案之间的关系进行对比学习，以生成完整的可行解，其质量可与 Gurobi 的最佳启发式解相媲美，且在整个数据集上表现优于最先进方法，提高了与最优值之间的差距，并且在所有数据集上保持超过 99.7% 的可行比率。

整数规划的有效可行解生成方法：引导扩散

Effective Generation of Feasible Solutions for Integer Programming via  Guided Diffusion

Graph problems such as traveling salesman problem, or finding minimal Steiner
trees are widely studied and used in data engineering and computer science.
Typically, in real-world applications, the features of the graph tend to change
over time, thus, finding a solution to the problem becomes challenging. The
dynamic version of many graph problems are the key for a plethora of real-world
problems in transportation, telecommunication, and social networks. In recent
years, using deep learning techniques to find heuristic solutions for NP-hard
graph combinatorial problems has gained much interest as these learned
heuristics can find near-optimal solutions efficiently. However, most of the
existing methods for learning heuristics focus on static graph problems. The
dynamic nature makes NP-hard graph problems much more challenging to learn, and
the existing methods fail to find reasonable solutions.
In this paper, we propose a novel architecture named Graph Temporal Attention
with Reinforcement Learning (GTA-RL) to learn heuristic solutions for
graph-based dynamic combinatorial optimization problems. The GTA-RL
architecture consists of an encoder capable of embedding temporal features of a
combinatorial problem instance and a decoder capable of dynamically focusing on
the embedded features to find a solution to a given combinatorial problem
instance. We then extend our architecture to learn heuristics for the real-time
version of combinatorial optimization problems where all input features of a
problem are not known a prior, but rather learned in real-time. Our
experimental results against several state-of-the-art learning-based algorithms
and optimal solvers demonstrate that our approach outperforms the
state-of-the-art learning-based approaches in terms of effectiveness and
optimal solvers in terms of efficiency on dynamic and real-time graph
combinatorial optimization.

本文提出一种名为 Graph Temporal Attention with Reinforcement Learning (GTA-RL) 的新型框架，针对动态组合优化问题学习启发式解决方案。该框架结构包括一个能够嵌入组合问题实例的时间特征的编码器和一个能够动态聚焦于嵌入特征以找到所需组合问题实例的解码器，并针对实时版本组合优化问题进行了扩展。实验证明，与现有方法相比，该方法在动态和实时图组合优化方面具有更高的效率和优化求解器的有效性。

使用多头注意力深度强化学习解决动态图问题

Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning

All Colors Shortest Path problem defined on an undirected graph aims at
finding a shortest, possibly non-simple, path where every color occurs at least
once, assuming that each vertex in the graph is associated with a color known
in advance. To the best of our knowledge, this paper is the first to define and
investigate this problem. Even though the problem is computationally similar to
generalized minimum spanning tree, and the generalized traveling salesman
problems, allowing for non-simple paths where a node may be visited multiple
times makes All Colors Shortest Path problem novel and computationally unique.
In this paper we prove that All Colors Shortest Path problem is NP-hard, and
does not lend itself to a constant factor approximation. We also propose
several heuristic solutions for this problem based on LP-relaxation, simulated
annealing, ant colony optimization, and genetic algorithm, and provide
extensive simulations for a comparative analysis of them. The heuristics
presented are not the standard implementations of the well known heuristic
algorithms, but rather sophisticated models tailored for the problem in hand.
This fact is acknowledged by the very promising results reported.

该篇论文介绍了一种定义在无向图上的全色最短路径问题，它旨在寻找一条最短路径，在路径中每种颜色至少出现一次，假设图中的每个顶点都与一个已知的颜色相关联。该论文证明了这个问题是 NP-hard 的，并提出了用 LP 松弛，模拟退火，蚁群算法和遗传算法等多种启发式方法来解决该问题，并进行了广泛的模拟来进行比较分析。