Abstract
We study the set of optimal solutions of the dual linear programming formulation of the linear assignment problem (LAP) to propose a method for computing a solution from the relative interior of this set. Assuming that an arbitrary dual-optimal solution and an optimal assignment are available (for which many efficient algorithms already exist), our method computes a relative-interior solution in linear time. Since LAP occurs as a subproblem in the linear programming relaxation of quadratic assignment problem (QAP), we employ our method as a new component in the family of dual-ascent algorithms that provide bounds on the optimal value of QAP. To make our results applicable to incomplete QAP, which is of interest in practical use-cases, we also provide a linear-time reduction from incomplete LAP to complete LAP along with a mapping that preserves optimality and membership in the relative interior. Our experiments on publicly available benchmarks indicate that our approach with relative-interior solution is frequently capable of providing superior bounds and otherwise is at least comparable.
Abstract (translated)
我们研究的是线性分配问题的二元线性 Programming formulation(LAP)的最佳解决方案集合,并提出了一种方法,从该集合的相对内部计算解决方案。假设有一个任意的二元最佳解决方案和最佳分配(许多高效的算法已经存在),我们的算法使用线性时间计算一个相对内部解决方案。由于LAP是在线性 Programming 放松 quadratic 分配问题(QAP)的问题作为子问题的情况下发生的,我们将其作为双升算法家族中的新组件。为了使我们的结果适用于在实际应用中感兴趣的不完整的 QAP,我们还提供了从不完整的 LAP 到完整的 LAP 的线性时间减少,并使用映射保持最优性和内部成员。我们公开基准测试的结果表明,我们的相对内部解决方案常常能够提供更好的限制,否则至少可以与之相当。
URL
https://arxiv.org/abs/2301.11201
