A Metaheuristic Optimization Algorithm for Binary Quadratic Problems

This paper focuses on the formulation and solution of binary quadratic problems. A new metaheuristic approach is presented in order to acquire good solutions. Computational results show that the heuristic solver finds good solutions quite fast. One of the test problems is tai256c, a gray-scale pattern problem by Taillard (1995) found in the QAPLIB (Burkard et al. (1997), http://www.seas.upenn.edu/qaplib/inst.html). The tai256c problem has been written in a quadratic form by Nissfolk et al. (2012) and then convexified using the QCR method by Billionnet et al. (2009). The algorithm is based on an iterative two-stage selection of variables to optimize. First the algorithm goes trough the vector of binary variables of length k, chooses the m-first variables (m < k) with a value of one and optimizes over them, and then continues to the m next variables with values of one and selects them for optimization. In these optimization steps the solution can either improve or stay the same. Once the algorithm has gone through the whole vector without improvement it randomly selects m variables with values of one to optimize and does this for a specified number of iterations.