Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion

可行解对于整数规划（IP）至关重要，因为它们可以大大加速求解过程。在许多应用中，相似的IP实例通常具有类似的结构和共享的解分布，这些可以潜在地通过深度学习方法进行建模。然而，现有的基于深度学习的算法，如神经潜水和预测搜索框架，仅限于生成部分可行解，并且必须依赖于像SCIP和Gurobi这样的求解器来完成给定IP问题的解。在本文中，我们提出了一种新的框架，可以端到端地生成完整的可行解。我们的框架利用对比学习来表征IP实例和解之间的关系，并学习IP实例和它们的解的潜在嵌入。此外，该框架采用扩散模型来学习在IP表示的条件下解嵌入的分布，具有专门的引导采样策略，考虑到约束和目标。我们在四个典型的IP问题数据集上进行了实证评估，并表明它可以在不依赖于求解器的情况下高概率（>89.7％）地有效生成完整的可行解，并且解的质量与Gurobi的最佳启发式解相当。此外，通过将我们方法的采样部分解与SCIP的CompleteSol启发式方法相结合，所得到的可行解在所有数据集上优于最先进的方法，展现出3.7到33.7％的最优值间隙改进，并保持所有数据集的可行比率超过99.7％。

本论文旨在解决整数规划（IP）中的可行解问题，提出了一种全新的框架，可以生成完整的可行解，而不需要依赖于求解器。

本论文的关键思路是利用对比学习来表征IP实例和解决方案之间的关系，并学习IP实例和其解决方案的潜在嵌入。此外，该框架采用扩散模型来学习在给定IP表示的情况下，解决方案嵌入的分布，并使用专用的引导采样策略来考虑约束和目标。

论文在四个典型的IP问题数据集上进行了实证评估，并展示了其在不依赖于求解器的情况下，能够高概率（>89.7%）地生成完整的可行解，并且其解的质量与Gurobi的最佳启发式解相当。此外，将本方法的采样部分解与SCIP的CompleteSol启发式算法相结合，得到的可行解在所有数据集上均优于最先进的方法，在最优值差距方面表现出3.7到33.7%的提高，并且保持了超过99.7%的可行比率。

近期的相关研究包括Neural Diving和Predict-and-search框架等基于深度学习的算法，但这些算法仅能生成部分可行解，并且必须依赖于SCIP和Gurobi等求解器来完成给定IP问题的解。