2021/01/01 by Koichi Fujii, Naoki Ito, Sunyoung Kim +4
Computer Science · Engineering · Mathematics · #Artificial intelligence #Bounding overwatch #Combinatorics #Computer science #Dimension (graph theory) #Generator (circuit theory) #Geometry #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Packing Problems #Optimization and Search Problems #Quadratic equation #Quadratic programming #Scale (ratio) #Scheduling and Optimization Algorithms #Upper and lower bounds #math.OC #msc:90C20 #msc:90C22
paper · pdf · doi:10.12752/8130
15 pages
openalex publication_date 2021/01/01 · arxiv created 2021/01/24 · arxiv updated 2021/01/26 · openalex created_date 2021/02/01 · openalex updated_date 2026/08/05
We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors’ group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results. Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.