一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique

In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

A contribution to quadratic assignment problems

We discuss special eases of the quadratic assignment problem (QAP) being polynomially solvable. In particular we give an algebraic condition for the cost; Matrices of a QAP which guarantees that it is equivalent with a linear assignment problem. Based on these results we develop an approximation algorithm for QAPs with non-negative symmetric cost matrices.     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n × n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation. The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size. Numerical experiments show that the reduced instances, with K ? n, can be solved exactly using standard MIP solvers.     

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et?al. (J Comb Optim 2:71–109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.     

One-dimensional machine location problems in a multi-product flowline with equidistant locations

An assignment of machines to locations along a straight track is required to optimize material flow in many manufacturing systems. The assignment of M unique machines to M locations along a linear material handling track with the objective of minimizing the total machine-to-machine material transportation cost is formulated as a quadratic assignment problem (QAP). The distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Since an optimal solution to a problem with large M is computationally intractable (the QAP is NP-hard), a number of the amoebic properties are exploited to devise heuristics and a lower bound on the optimal solution. Computational results which demonstrate the performance of the heuristics and the lower bound are presented.     

Generating Hard Test Instances with Known Optimal Solution for the Rectilinear Quadratic Assignment Problem

In this paper we consider the rectilinear version of the quadratic assignment problem (QAP). We define a class of edge-weighted graphs with nonnegatively valued bisections. For one important type of such graphs we provide a characterization of point sets on the plane for which the optimal value of the related QAP is zero. These graphs are used in the algorithms for generating rectilinear QAP instances with known provably optimal solutions. The basic algorithm of such type uses only triangles. Making a reduction from 3-dimensional matching, it is shown that the set of instances which can be generated by this algorithm is hard. The basic algorithm is extended to process graphs larger than triangles. We give implementation details of this extension and of four other variations of the basic algorithm. We compare these five and also two existing generators experimentally employing multi-start descent heuristic for the QAP as an examiner. The graphs with nonnegatively valued bisections can also be used in the construction of lower bounds on the optimal value for the rectilinear QAP.     

A branch-and-bound algorithm for the singly constrained assignment problem

The singly constrained assignment problem (SCAP) is a linear assignment problem (LAP) with one extra side constraint, e.g., due to a time restriction. The SCAP is, in contrast to the LAP, difficult to solve. A branch-and-bound algorithm is presented to solve the SCAP to optimality. Lower bounds are obtained by Lagrangean relaxation. Computational results show that the algorithm is able to solve different types of SCAP instances up to size n = 1000 within short running times on a standard personal computer.     

Global optimality conditions and optimization methods for quadratic assignment problems

In this paper some global optimality conditions for general quadratic {0, 1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods.     

A GRASP for the biquadratic assignment problem

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). It is a nonlinear integer programming problem where the objective function is a fourth degree multivariable polynomial and the feasible domain is the assignment polytope. BiQAP problems appear in VLSI synthesis. Due to the difficulty of this problem, only heuristic solution approaches have been proposed. In this paper, we propose a new heuristic for the BiQAP, a greedy randomized adaptive search procedure (GRASP). Computational results on instances described in the literature indicate that this procedure consistently finds better solutions than previously described algorithms.     

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

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

GRASP with path-relinking for the generalized quadratic assignment problem

The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.     

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.     

Minimum energy configurations on a toric lattice as a quadratic assignment problem

We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.     

Approximate solutions to the turbine balancing problem

The turbine balancing problem (TBP) is an NP-Hard combinatorial optimization problem arising in the manufacturing and maintenance of turbine engines. Exact solution methods for solving the TBP are not appropriate since the problem has to be solved in real time and the input data is itself inaccurate. In this paper the TBP is formulated as a quadratic assignment problem (QAP) and we propose a heuristic algorithm for solving the resulting problem. Computational results on a set of instances provided by Pratt & Whitney (P&W) and from the literature, indicate that the proposed algorithm outperforms the current methods used for solving the TBP, and has the best overall performance with respect to other heuristic algorithms in the literature.     

Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems

A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing.     

Ant colony optimization for solving an industrial layout problem

This paper presents ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem. ACO_GLS is applied to an industrial case, in a train maintenance facility of the French railway system (SNCF). Results show that an improvement of near 20% is achieved with respect to the actual layout. Since the problem is modeled as a quadratic assignment problem (QAP), we compared our approach with some of the best heuristics available for this problem. Experimental results show that ACO_GLS performs better for small instances, while its performance is still satisfactory for large instances.