Quadratic Assignment Using Majorization-Minimization and Collaborative Neurodynamic Optimization

The quadratic assignment problem (QAP) is a fundamental NP-hard combinatorial optimization problem characterized by a quadratic objective and discrete permutation constraints. Continuous relaxation makes neurodynamic optimization applicable to QAP, but a single search trajectory may converge to a poor local solution because the relaxed problem is nonconvex. To address these challenges, a collaborative neurodynamic optimization (CNO) framework integrating majorization-minimization (MM) and a momentum recurrent neural network (MRNN), termed CNO-MM-MRNN, is proposed. MM constructs quadratic surrogate subproblems for a penalized doubly stochastic relaxation, and the MRNN approximately solves these subproblems to refine each candidate. Multiple candidates exchange personal-best and global-best information to explore different attraction regions. Feasible permutations decoded from relaxed matrices are evaluated using the original QAP objective, which primarily guides the selection of personal-best and global-best records. The selected assignments are fed back into the continuous candidate states to guide subsequent updates. The best, average, and worst percentage deviations (BPD, APD, and WPD), averaged over fifteen QAPLIB instances, are 0.144%, 0.192%, and 0.245%, respectively. The inner MM and global-attainment results depend on assumptions that are not fully established for the finite-step implementation. They therefore do not guarantee finite-budget global optimality.