A New Heuristic for the Quadratic Assignment Problem

We propose a new heuristic for the solution of the quadratic assignment problem. The heuristic combines ideas from tabu search and genetic algorithms. Run times are very short compared with other heuristic procedures. The heuristic performed very well on a set of test problems.     

An Improved Heuristic for the Quadratic Assignment Problem

A technique is described whereby the computational efficiency of the Lashkari-Jaisingh heuristic for the quadratic assignment problem is greatly enhanced. Results for the modified heuristic are presented which demonstrate that it provides solutions of consistently high quality at relatively small computational cost.     

A Heuristic Approach to Quadratic Assignment Problem

A new algorithm for solving quadratic assignment problems is presented. The algorithm, which employs a sequential search technique, constructs a matrix of lower bounds on the costs of locating facilities at different sites. It then improves the elements of this matrix, one by one, by solving a succession of linear assignment problems. After all the elements of the matrix are improved, a feasible assignment is obtained, which results in an improved value for the objective function of the quadratic assignment problem. The procedure is repeated until the desired accuracy in the objective function value is obtained.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

On the Hardness of the Quadratic Assignment Problem with Metaheuristics

Meta-heuristics are a powerful way to approximately solve hard combinatorial optimization problems. However, for a problem, the quality of results can vary considerably from one instance to another. Understanding such a behaviour is important from a theoretical point of view, but also has practical applications such as for the generation of instances during the evaluation stage of a heuristic.In this paper we propose a new complexity measure for the Quadratic Assignment Problem in the context of metaheuristics based on local search, e.g. simulated annealing. We show how the ruggedness coefficient previously introduced by the authors, in conjunction with the well known concept of dominance, provides important features of the search space explored during a local search algorithm, and gives a rather precise idea of the complexity of an instance for these heuristics. We comment previous experimental studies concerning tabu search methods and genetic algorithms with local search in the light of our complexity measure. New computational results with simulated annealing and taboo search are presented.     

Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

A Hybrid Metaheuristic for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%. This work was supported in part by the National Science Council, R.O.C., under Contract NSC 91-2213-E-005-017.     

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

The Use of Specially Structured Models for Obtaining Bounds in the Quadratic Assignment Problem

In this paper we study a procedure for finding bounds for the quadratic assignment problem. This procedure may be used as a sub-routine in hybrid procedures for solving this problem. The approach is based upon a data decomposition method, linking the actual data to the data of a special class of assignment problems for which bounds are computationally tractable.     

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.     

Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem

We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant. This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science Department of Darmstadt University of Technology, Germany     

On the Hyers-Ulam Stability Problem for Quadratic Multi-dimensional Mappings on the Gaussian Plane

In this paper we solve the Hyers-Ulam stability problem for quadratic multidimensional mappings on the Gaussian plane.AMS Subject Classification (1991): 39B     

求解标准二次优化问题的割平面算法

标准的二次优化问题是NP-hard问题,把该问题转化为半不定的线性规划问题,且提出了一个线性规划的割平面算法来求解这个半不定的线性规划问题,并给出了该算法的收敛性证明.     

Heuristic Methods for the Data Placement Problem

Databases require a management system which is capable of retrieving and storing information as efficiently as possible. The data placement problem is concerned with obtaining an optimal assignment of data tuples onto secondary storage devices. Such tuples have complicated interrelationships which make it difficult to find an exact solution to our problem in a realistic time.We therefore consider heuristic methods—three of which are discussed and compared — the ‘greedy’ graph-collapsing method, the probabilistic hill-climbing method of simulated annealing and a third ‘greedy’ heuristic, the random improvement method, which is a local search heuristic. Overall, the best performance is obtained from the graph-collapsing method for the less complicated situations, but for larger-scale problems with complex interrelationships between tuples the simulated annealing and random improvement algorithms give better results.     

Nested Heuristic Methods for the Location-Routeing Problem

The concept of ‘nested methods’ is adopted to solve the location-routeing problem. Unlike the sequential and iterative approaches, in this method we treat the routeing element as a sub-problem within the larger problem of location. Efficient techniques that take into account the above concept and which use a neighbourhood structure inspired from computational geometry are presented. A simple version of tabu search is also embedded into our methods to improve the solutions further. Computational testing is carried out on five sets of problems of 400 customers with five levels of depot fixed costs, and the results obtained are encouraging.     

几种基于匈牙利算法求解二次分配问题的方法及其分析比较

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。二次分配问题的线性化模型和下界计算方法,是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础,根据现有QAP对偶上升下界计算方法中的具体操作,提出几种可行的QAP对偶上升计算新方法。最后,通过求解QA-PLIB中的部分实例,深入分析其运行结果,详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度,这为基于匈牙利算法求解二次分配问题的方法的改进奠定了基础。     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods

This paper reports heuristic and exact solution advances for the Quadratic Assignment Problem (QAP).QAPinstances most often discussed in the literature are relatively well solved by heuristic approaches. Indeed, solutions at a fraction of one percent from the best known solution values are rapidly found by most heuristic methods. Exact methods are not able to prove optimality for these instances as soon as the problem size approaches 30 to 40. This article presents new QAP instances that are ill conditioned for many metaheuristic-based methods. However, these new instances are shown to be solved relatively well by some exact methods, since problem instances up to a size of 75 have been exactly solved.     

Heuristic Methods for the Multi-product Dynamic Lot Size Problem

Many heuristics exist for the single-item dynamic lot-size problem, for example, the Silver-Meal, the part period balancing and a simple variant of the part period balancing. The worst case performances of these heuristics have been shown to be zero, 1/3 and 1/2 respectively. These heuristics can be generalized to the dynamic version of the joint replenishment problem, that is, the multi-product dynamic lot-size problem. Such a generalization of the Silver-Meal heuristic has been shown to perform well on a set of test problems. This paper generalizes the part period balancing heuristic, and a simple variant of it to the multiproduct dynamic lot-size problem, and shows that the worst case performances of the generalized heuristics remain 1/3 and 1/2 respectively. An improved version of the generalized Silver-Meal heuristic is also given.     

A Lagrangean Relaxation Approach for a Turbine Design Quadratic Assignment Problem

In this paper we show how a Lagrangean relaxation approach to a turbine design problem results in a relatively easy set of Lagrangean subproblems to solve, because of the particular structure of the turbine design problem.