Search

Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB (Quadratic Assignment Problem Library) test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances. [ABSTRACT FROM AUTHOR]

In this article, we present a multi-start approach to solve a determinant maximization problem of an integer matrix variable that has a constant trace. In order to enforce that elements of the matrix variable are integer, we add a nonlinear repeller term to the objective function. To solve this nonlinear optimization problem we implement our sequential conic trust-region-based algorithm within a multi-start framework. To demonstrate the potential of our approach, we use a determinant maximization model from crystallography. [ABSTRACT FROM PUBLISHER]