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


An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n4) … Read more

On semidefinite programming bounds for graph bandwidth

We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more

A Feasible method for Optimization with Orthogonality Constraints

Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. … Read more

SDP relaxations for some combinatorial optimization problems

In this chapter we present recent developments on solving various combinatorial optimization problems by using semidefinite programming (SDP). We present several SDP relaxations of the quadratic assignment problem and the traveling salesman problem. Further, we show the equivalence of several known SDP relaxations of the graph equipartition problem, and present recent results on the bandwidth … Read more

Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers

The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearization are tight, but hardly exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation [1] is … Read more

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71–109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP … Read more

Effective formulation reductions for the quadratic assignment problem

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson [2] integer linear programming formulation of the QAP, which we call formulation IPQAP-I. We analyze two cases: In the first case, we study the effect of constraint reduction. … Read more

Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB – a quadratic assignment problem … 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