Search

Quadratic Assignment Problem (QAP) is one extension of the assignment problem by setting n facilities to n certain locations to minimize the total assignment costs. QAP is also a combinatorial optimization problem that is a problem that has a finite set of solutions. Basically the solution of combinatorial problems can be obtained with the right results but for complex problems with larger data sizes it is quite difficult to calculate because the time used is long enough for the completion process. One of the algorithms implemented in the completion of QAP is the Ant Colony Optimization (ACO) algorithm is an algorithm that mimics the behavior of ants in finding food from the nest to a food source with the help of indirect communication called pheromone, so that pheromone is used to find optimal solutions with quite a short time. in this research ACO is used to solve the QAP problem by using a random proportional of rule formula then getting the smallest solution and renewing the pheromone until the assignment is stable and the solution obtained is fixed until the maximum assignment solution. The results obtained to complete the Quadratic Assignment Problem with the Ant Colony Optimization algorithm to get a solution to the QAP problems tested in the Nugent case resulted in a more minimal solution and the placement of appropriate location facilities through pheromone assistance and stored in a taboo list so that all facilities get a decent location with a worth it short time in completion.

By now, many copositive reformulations of mixed-binary QPs have been discussed, triggered by Burer's seminal characterization from 2009. In conic optimization, it is very common to use approximation hierarchies based on positive-semidefinite (psd) matrices where the order increases with the level of the approximation. Our purpose is to keep the psd matrix orders relatively small to avoid memory size problems in interior point solvers. Based upon on a recent discussion on various variants of completely positive reformulations and their relaxations (Bomze et al. in Math Program 166(1–2):159–184, 2017), we here present a small study of the notoriously hard multidimensional quadratic knapsack problem and quadratic assignment problem. Our observations add some empirical evidence on performance differences among the above mentioned variants. We also propose an alternative approach using penalization of various classes of (aggregated) constraints, along with some theoretical convergence analysis. This approach is in some sense similar in spirit to the alternating projection method proposed in Burer (Math Program Comput 2:1–19, 2010) which completely avoids SDPs, but for which no convergence proof is available yet. [ABSTRACT FROM AUTHOR]

Multi-objective facility layout problem (mFLP) generates a different layout by varying objectives weights. Since the selection of objective weights in mFLP is critical, stages of designing layout having multiple objectives, the objective weights therefore play an important role in the layout design of mFLP. In practice, it is selected randomly by the layout designer based on his/her past experience that restricts the layout designing process completely designer dependent and thus the layout varies from designer to designer. This paper aims to resolve the issues of selecting the objective weight for each objective. We propose four methods to determine objective weight which makes the design process of mFLP completely designer independent. [ABSTRACT FROM AUTHOR]

We consider a generalization of the classical quadratic assignment problem, where material flows between facilities are uncertain, and belong to a budgeted uncertainty set. The objective is to find a robust solution under all possible scenarios in the given uncertainty set. We present an exact quadratic formulation as a robust counterpart and develop an equivalent mixed integer programming model for it. To solve the proposed model for large-scale instances, we also develop two different heuristics based on 2-Opt local search and tabu search algorithms. We discuss performance of these methods and the quality of robust solutions through extensive computational experiments.

Virtualization is one of the core technologies used in cloud computing to provide services on demand for end users over the Internet. Most current research allocates virtual machines to physical machines based on CPU utilization. However, for many applications that require communication between services running on different servers, communication costs influence the overall performance. Therefore, this study focuses on the optimal allocation of virtual machines across multiple geographically dispersed data centers, with the objective of minimizing communication costs. The original problem can be constructed as a quadratic assignment problem that is a classical NP-hard combinatorial optimization problem. This study adopts an efficient deterministic optimization approach to reformulate the original problem as a mixed-integer linear program that may be solved to obtain a globally optimal solution. Since the required bandwidth matrix and communication cost matrix are symmetric, the mathematical model of virtual machine placement can be simplified. Several numerical examples drawn from the literature are solved to demonstrate the computational efficiency of the proposed method for determining the optimal virtual machine allocation in cloud computing.

Abstract: In this article we provide an exact expression for computing the autocorrelation coefficient and the autocorrelation length of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters and for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem. [Copyright &y& Elsevier]

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = (ai j ) and B = (bi j ). The objective is to compute a permutation p of V = {1, …, n} so that Σ i, jϵV i≠j aπ(i),π( j)bi, j is minimized. We assume that A is a 0/1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of the orthogonal similarity set of the quadratic part of the objective function. This exploits the matrix structure of QAP and results in a relaxation with much smaller dimension than other current SDP relaxations. We compare the resulting bounds with several other computationally inexpensive bounds such as the convex quadratic programming relaxation (QPB). We find that our method provides stronger bounds on average and is adaptable for branch-and-bound methods. [ABSTRACT FROM AUTHOR]

Abstract: Semidefinite relaxations of the quadratic assignment problem () have recently turned out to provide good approximations to the optimal value of . We take a systematic look at various conic relaxations of . We first show that can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over this cone, we also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. It is still a challenging task to solve the strongest of these models to reasonable accuracy on instances of moderate size. [Copyright &y& Elsevier]

Similarity of edge labeled graphs is considered in the sense of minimum squared distance between corresponding values. Vertex correspondences are established by isomorphisms if both graphs are of equal size and by subisomorphisms if one graph has fewer vertices than the other. Best fit isomorphisms and subisomorphisms amount to solutions of quadratic assignment problems and are computed exactly as well as approximately by minimum cost flow, linear assignment relaxations and related graph algorithms. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems. [ABSTRACT FROM AUTHOR]

We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values -1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem. [ABSTRACT FROM AUTHOR]

In regular optimal-control problems, Pontryagin's maximum principle specifies possible optimal solutions among trajectories of a Hamiltonian system. In this paper, we show how to extend this approach to singular linear-quadratic optimal-control problems that have only "generalized" optimal solutions. We define generalized Hamiltonian flows whose trajectories are distributions (generalized functions). We show that generalized Hamiltonian trajectories correspond to the generalized optimal solutions of the problem and obtain a geometric description of the generalized optimal synthesis for singular linear-quadratic problems. [ABSTRACT FROM AUTHOR]

For $m\ge 1$, let $\alpha : \alpha _{0}<\cdots <\alpha _{m}$ be a collection of ($m+1$) positive weights. The \emph{Quadratically Hyponormal Completion Problem} seeks necessary and sufficient conditions on $\alpha $ to guarantee the existence of a quadratically hyponormal unilateral weighted shift $W$ with $\alpha $ as the initial segment of weights. We prove that $\alpha $ admits a quadratically hyponormal completion if and only if the self-adjoint $m\times m$ matrix \begin{equation*}D_{m-1}(s):= \begin{pmatrix}q_{0}&\bar r_{0}&0&\hdots &0&0 r_{0}&q_{1}&\bar r_{1}&\hdots &0&0 0&r_{1}&q_{2}&\hdots &0&0 \vdots &\vdots &\vdots &\ddots &\vdots &\vdots 0&0&0&\hdots &q_{m-2}&\bar r_{m-2} 0&0&0&\hdots &r_{m-2}&q_{m-1}\end{pmatrix} \end{equation*} is positive and invertible, where $q_{k}:=u_{k}+|s|^{2} v_{k}$, $r_{k}:=s\sqrt {w_{k}}$, $u_{k}:=\alpha _{k}^{2}-\alpha _{k-1}^{2}$, $v_{k}:=\alpha _{k}^{2}\alpha _{k+1}^{2}-\alpha _{k-1}^{2}\alpha _{k-2}^{2}$, $w_{k}:=\alpha _{k}^{2}(\alpha _{k+1}^{2}-\alpha _{k-1}^{2})^{2}$, and, for notational convenience, $\alpha _{-2}=\alpha _{-1}=0$. As a particular case, this result shows that a collection of {\em four} positive numbers $\alpha _{0}<\alpha _{1}<\alpha _{2}<\alpha _{3}$ {\em always} admits a quadratically hyponormal completion. This provides a new qualitative criterion to distinguish quadratic hyponormality from 2-hyponormality. [ABSTRACT FROM AUTHOR]

A primal-dual active set method for quadratic problems with bound constraints is presented. Based on a guess on the active set, a primal dual pair (x, s) is computed that satisfies the first order optimality condition and the complementarity condition. If (x, s) is not, feasible, a new active sat is determined, and the process is iterated. Sufficient conditions for the iterations to stop in a finite number of steps with an optimal solution are provided. Computational experience indicates that this approach often requires only a few (less than 10) iterations to find the optimal solution. [ABSTRACT FROM AUTHOR]

A new approach to evaluate lower bounds for a class of quadratic assignment problems (QAP) is presented. An instance of a QAP of size n is specified by two n × n matrices D and F, and is denoted by QAP(D, F). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices Fopt and Fres are constructed such that F = Fopt + Fres, and the optimal solution to QAP(D, Fopt) is known. Any existing lower bound can then be applied to QAP(D, Fres), which in sum with the optimal value for QAP(D, Fopt), provides a lower bound to QAP(D, F). Thus, this method could serve as a reduction process to possibly improve the results from a variety of bounding techniques. This approach is tested on two bounds from the literature, the Gilmore-Lawler bound (GLB) and an eigenvalue bound (PB), for various problems of size ranging from 6-49. Computational results show a good improvement in bounds for all the test problems. An extension of our method to a more general class of QAPs is also presented. [ABSTRACT FROM AUTHOR]

New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound is easy to implement and often provides high quality bounds under an acceptable computational effort [ABSTRACT FROM AUTHOR]

For the general quadratic assignment problem as well as for a planar version of this problem, we extend earlier work by Burkard and Fincke to prove that the ratio of the maximal to the minimal solution value converges to 1 almost surely. In fact, any solution value can almost surely be written asymptotically as a simple, explicitly given function of the problem size. Theoretical analysis and computational experiments reveal the convergence to be relatively fast. [ABSTRACT FROM AUTHOR]

The Quadratic Assignment Problem QAP is formulated as a Quadratic Set Packing problem QSP using a Lagrangian Relaxation to transform the original QSP into a Relaxed Assignment problem. Special features of the Relaxed Assignment problem allow us to incorporate vital multi-attribute characteristics of the QSP into the nonlinear part of the objective function. The multi-attribute characteristics which directly affect our Relaxed Assignment formulation are demonstrated for facility layout and location problems. In addition, an exact branch and bound algorithm entitled MAFLAD (Multi-Attribute Facility Layout and Design), is developed which utilizes pre-processing of the decision variables, the constraints and nonlinear part of the objective function to optimally solve the QSP. Finally, a set of three alternative heuristic strategies within MAFLAD are examined for their effectiveness in pruning and searching the enumeration tree. Computational results of the branch and bound algorithm on a VAX 11-785 are presented to demonstrate the scope and limitations of the procedure. [ABSTRACT FROM AUTHOR]