整数规划的自回归可微方法

arXiv:2610.02528v1 公告类型：新 摘要：我们提出了一种用于求解 0-1 整数规划的自回归可微方法。我们固定二元变量的任意顺序，并训练一个 transformer 在保持位于可行集内的同时预测下一个比特。我们的方法首先利用任意求解器提供的可行当前最优解进行训练，从而能够将 transformer 初始化在可行集内。随后，我们的过程引入拉格朗日惩罚以惩罚不可行解，并使用松弛目标上的 Gumbel-softmax 激活函数，进一步训练 transformer 来探索可行集。我们在非凸二次背包问题实例上测试了该方法，并证明对于最多包含 10,000 个二元变量的稠密问题，该方法相较于当前最先进的开源求解器能够持续取得改进。特别是，我们通过实验证明了一种类似于隧穿效应的现象：该方法将变量从二元变量转换为 transformer 的连续权重，这种转换使其能够跨越松弛目标景观中的障碍。