Semidefinite programming approach for the quadratic assignment problem with a sparse graph

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension \(n^2\) where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension \(\mathcal {O}(n)\) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension \(\mathcal {O}(n)\). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A generalized design approach to solution of the non-convex quadratic programming problem

This paper outlines a generalized, systematic design approach to solution of the non-convex quadratic programming problem. It is based on a previous formulation of utility of a general system in terms of efficiency and robustness of the system. The approach is to introduce a robustness term of arbitrary magnitude into the design utility function. Mathematically, this makes the problem convex. From a design approach, it yields a more general solution allowing specialization to proceed by decreasing robustness (on an initially convex utility surface in the feasible design space) until the region of the overall optimum is approached. The approach is mathematically related to the Metropolis technique of simulated annealing but a more systematic (less random) solution process is used. It is analogous also to the heuristic technique of Burkard and Bonniger. These two previous techniques are the most effective so far reported for the quadratic programming problem. The robustness approach provides an underpinning for each and opens up further solution options. Applications include layout of buildings and other constructed facilities and information technology layout problems.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

Lower bounds based on linear programming for the quadratic assignment problem

In this paper we prove that the Classical Gilmore-Lawler lower bound for the quadratic assignment problem is equivalent to a solution of a certain linear programming problem. By adding additional constraints to this linear programming problem we derive a lower bound which is at least as good as the Gilmore-Lawler lower bound.Some of this research was done while the author was on sabbatical leave at the Department of Management, The Hong Kong University of Science and Technology, Kowloon, Hong Kong.     

A column generation approach for the unconstrained binary quadratic programming problem

This paper proposes a column generation approach based on the Lagrangean relaxation with clusters to solve the unconstrained binary quadratic programming problem that consists of maximizing a quadratic objective function by the choice of suitable values for binary decision variables. The proposed method treats a mixed binary linear model for the quadratic problem with constraints represented by a graph. This graph is partitioned in clusters of vertices forming sub-problems whose solutions use the dual variables obtained by a coordinator problem. The column generation process presents alternative ways to find upper and lower bounds for the quadratic problem. Computational experiments were performed using hard instances and the proposed method was compared against other methods presenting improved results for most of these instances.     

A survey for the quadratic assignment problem

The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.     

An explicit linear solution for the quadratic dynamic programming problem

For a given vectorx ₀, the sequence {x _t} which optimizes the sum of discounted rewardsr(x _t, x_t+1), wherer is a quadratic function, is shown to be generated by a linear decision rulex _t+1=Sx _t +R. Moreover, the coefficientsR,S are given by explicit formulas in terms of the coefficients of the reward functionr. A unique steady-state is shown to exist (except for a degenerate case), and its stability is discussed.     

Linear programming insights into solvable cases of the quadratic assignment problem

The quadratic assignment problem is an NP-hard discrete optimization program that has been extensively studied for over 50 years. It has a variety of applications in many fields, but has proven itself extremely challenging to solve. As a result, an area of research has been to identify special cases which admit efficient solution strategies. This paper examines four such cases, and shows how each can be explained in terms of the dual region to the continuous relaxation of a classical linear reformulation of the problem known as the level-1 RLT representation. The explanations allow for simplifications and/or generalizations of the conditions defining the special cases.     

Biological computation of the solution to the quadratic assignment problem

Biological computing provides a promising approach to attacking computationally intractable problems. The quadratic assignment problem (QAP) is a well-known NP-hard combinatorial optimization problem. This paper addresses the problem of how to solve QAP under the Adleman–Lipton-sticker model. A theoretically efficient DNA algorithm for solving QAP is proposed, which is executed by performing O(Kn⁴) operations on test tubes of DNA molecular strands with n² + K + 1 bit regions, where n is the number of facilities, and K is the length of the binary representation of an upper bound on the objective function. With the rapid progress of molecular biology techniques, the proposed algorithm might be of practical use in treating medium-sized instances of QAP.     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

Linear,quadratic, and bilinear programming approaches to the linear complementarity problem

Traditional pivoting procedures for solving the linear complementarity problem can only guarantee convergence for problems having well defined structures. Recently, optimization procedures based on linear, quadratic, and bilinear programming have been developed to extend the class of problems that can be solved efficiently. These latter approaches are the focus of this paper.The strengths and weaknesses of each of the approaches are discussed. The linear programming approach, advanced by Mangasarian, is the most efficient once an appropriate objective function is found. This requires the solution of a system of linear and bilinear equations that is easily solvable only in some cases. Extensions to this approach, due to Shiau, show some promise but are still limited to special cases of the general problem. The quadratic programming approaches discussed here are restricted to specialized procedures for the complementarity problem. One, proposed by Cheng, is based on the levitin-Poljak gradient projection method, and the other, due to Cirina, is based on Karush-Kuhn-Tucker theory. Both are only successful on some problems. The two bilinear programming algorithms discussed are the most general. For any problem, they are guaranteed to find at least one solution or conclude that none exist. One is a specialization of the recent biconvex programming algorithm of Al-Khayyal and Falk and the other is an entirely new implicit enumeration procedure.     

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: (Burkard et al. in J Global Optim 10:291–403, 1997).     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…     

Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada.     

A new greedy algorithm for the quadratic assignment problem

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.     

一类特殊二次分配问题的线性化求解新方法

许多抽象于实际的二次分配问题,其流矩阵与距离矩阵中有很多零元素,求解该类二次分配问题时,可通过先行利用零元素的信息减小问题规模,缩短计算时间．以二次分配问题的线性化模型为基础,提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法,不仅从理论上证明了方法的可行性,而且从实验的角度说明了该方法比以往方法更加优越．     

A heuristic procedure for solving the quadratic assignment problem

An heuristic approach to the solution of the quadratic assignment problem is presented. A simple procedure is used to get a good feasible starting point, then the problem is solved as a nonlinear program (ignoring the integrality conditions) using MINOS, and lastly the near integer solution is converted into an integer feasible solution using an heuristic procedure. The results compare favourably with other procedures in the literature. A superior solution to the 19 × 19 hospital layout problem is found.