Characterizing Linearizable QAPs by the Level-1 Reformulation-Linearization Technique

The quadratic assignment problem (QAP) is an extremely challenging NP-hard combinatorial optimization program. Due to its difficulty, a research emphasis has been to identify special cases that are polynomially solvable. Included within this emphasis are instances which are linearizable; that is, which can be rewritten as a linear assignment problem having the property that the … Read more

A Restricted Dual Peaceman-Rachford Splitting Method for QAP

We revisit and strengthen splitting methods for solving doubly nonnegative, DNN, relaxations of the quadratic assignment problem, QAP. We use a modified restricted contractive splitting method, rPRSM, approach. Our strengthened bounds and new dual multiplier estimates improve on the bounds and convergence results in the literature. Citation Department of Combinatorics & Optimization, University of Waterloo, … Read more

On Modeling Local Search with Special-Purpose Combinatorial Optimization Hardware

As we approach the physical limits predicted by Moore’s law, a variety of specialized hardware is emerging to tackle specialized tasks in different domains. Within combinatorial optimization, adiabatic quantum computers, CMOS annealers, and optical parametric oscillators are few of the emerging specialized hardware technology aimed at solving optimization problems. In terms of mathematical framework, the … Read more

Facial Reduction for Symmetry Reduced Semidefinite Programs

We consider both facial and symmetry reduction techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. The combination of facial and symmetry reduction leads to a significant improvement in both numerical stability and running time for both the ADMM and interior … Read more

Combinatorial Optimization Problems in Engineering Applications

This paper deals with several combinatorial optimization problems. The most challenging such problem is the quadratic assignment problem. It is considered in both two dimensions (QAP) and in three dimensions (Q3AP) and in the context of communication engineering. Semidefinite relaxations are used to derive lower bounds for the optimum while heuristics are applied to either … Read more

ADMM for the SDP relaxation of the QAP

The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the … Read more

hBcnorm regularization algorithms for optimization over permutation matrices

Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more

A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the … Read more

Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout

In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also … Read more

Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274–1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more