Relative-Interior Solution for the (Incomplete) Linear Assignment Problem with Applications to the Quadratic Assignment Problem
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 the LAP occurs as a subproblem in the linear programming (LP) relaxation of the 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 the QAP. To make our results applicable to the incomplete QAP, which is of interest in practical use-cases, we also provide a linear-time reduction from the incomplete LAP to the 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 can frequently provide bounds near the optimum of the LP relaxation and its runtime is much lower when compared to a commercial LP solver.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
RoSI: Recovering 3D Shape Interiors from Few Articulation Images
The dominant majority of 3D models that appear in gaming, VR/AR, and those we use to train geometric deep learning algorithms are incomplete, since they are modeled as surface meshes and missing their interior structures…
ObjectGOATex: Geometry & Occlusion-Aware Texturing
We present GOATex, a diffusion-based method for 3D mesh texturing that generates high-quality textures for both exterior and interior surfaces. While existing methods perform well on visible regions, they inherently lack…
Optimal Power Flow Solutions via Noise-Resilient Quantum-Inspired Interior-Point Methods
This paper presents three quantum interior-point methods (QIPMs) tailored to tackle the DC optimal power flow (DCOPF) problem using noisy intermediate-scale quantum devices. The optimization model is redefined as a linea…
WeaveNet for Approximating Assignment Problems
Assignment, a task to match a limited number of elements, is a fundamental problem in informatics. Many assignment problems have no exact solvers due to their NP-hardness or incomplete input, and their approximation alg…
Hessian barrier algorithms for linearly constrained optimization problems
In this paper, we propose an interior-point method for linearly constrained optimization problems (possibly nonconvex). The method - which we call the Hessian barrier algorithm (HBA) - combines a forward Euler discretiza…