A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting

Quadratic assignment problems (QAPs) are among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings … Read more

Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more

Graph Modeling for Quadratic Assignment Problem Associated with the Hypercube

In the paper we consider the quadratic ssignment problem arising from channel coding in communications where one coefficient matrix is the adjacency matrix of a hypercube in a finite dimensional space. By using the geometric structure of the hypercube, we first show that there exist at least $n$ different optimal solutions to the underlying QAPs. … Read more

A Server for Automated Performance Analysis of Benchmarking Data

As part of Performance World, we describe an automation server (PAVER: http://www.gamsworld.org/performance/paver) to help facilitate reproducible performance analysis of benchmarking data for optimization software. Although PAVER does not solve optimization problems, it automates the task of performance data analysis and visualization, taking into account various performance metrics. These include not only robustness and efficiency, but … Read more

An Independent Benchmarking of SDP and SOCP Solvers

This work reports the results of evaluating all computer codes submitted to the Seventh DIMACS Implementation Challenge on Semidefinite and Related Optimization Problems. The codes were run on a standard platform and on all the benchmark problems provided by the organizers of the challenge. A total of ten codes were tested on fifty problems in … Read more

Sufficient Optimality in a Parabolic Control Problem

We define a class of parabolic problems with control and state constraints and identify a problem within this class which possesses a locally unique critical point satisfying the second order sufficient optimality conditions. In this solution inequality constraints on the control are strongly active. The second derivative of the Lagrangian is not globally coercive. This … Read more