2020/05/13 by Juan Ignacio Mulero-Martínez, Mulero-Martínez, Juan Ignacio
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2005.07030
openalex publication_date 2020/05/13 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In this paper, an exact algorithm in polynomial time is developed to solve\nunrestricted binary quadratic programs. The computational complexity is\nO\( n\(15)/(2)\) , although very conservative, it is\nsufficient to prove that this minimization problem is in the complexity class\nP. The implementation aspects are also described in detail with a special\nemphasis on the transformation of the quadratic program into a linear program\nthat can be solved in polynomial time. The algorithm was implemented in MATLAB\nand checked by generating five million matrices of arbitrary dimensions up to\n30 with random entries in the range \[ -50,50\] . All the\nexperiments carried out have revealed that the method works correctly.\n