持续扩展组合优化目标是一种强大的技术,通常应用于集函数的优化。 然而,很少有这样的方法来扩展排列上的函数,尽管许多组合优化问题,如二次赋值问题(QAP)和旅行销售人员问题(TSP),本质上是对排列的优化。 我们介绍了Birkhoff Extension(BE),这是任何对数到倍态矩阵的排列上任何实值函数的几乎无处不在的可位连续多时可计算扩展。 这种构造的关键是我们引入了众所周知的Birkhoff分解的连续变体。 我们的扩展有几个不错的属性,使它吸引优化问题。 首先,BE提供了一个四舍五入保证,即任何扩展的解决方案都可以有效地四舍五入到排列而不增加函数值。 此外,在松弛的情况下,一个近似的解决方案将在排列的空间中产生一个近似的解决方案。 其次,使用BE,在排列上的任何实值优化目标都可以扩展到一个几乎无处不在的可微分的客观函数,而不是双随机矩阵的空间。 这使得我们的BE不仅能够适应基于梯度下降的优化,而且还可以进行无监督的神经组合优化,其中训练通常需要不同的损失。 第三,基于上述属性,我们提出了一个简单的优化过程,可以很容易地与现有的优化方法相结合,以提供局部改进(即最终解决方案的质量不比初始解决方案差)。 最后,我们还调整我们的扩展,以适应一类树的优化问题,例如Steiner树和基于优化的分层聚类。