Search

We consider new polynomially solvable cases of the well-known Quadratic Assignment Problem involving coefficient matrices with a special diagonal structure. By combining the new special cases with polynomially solvable special cases known in the literature we obtain a new and larger class of polynomially solvable special cases of the QAP where one of the two coefficient matrices involved is a Robinson matrix with an additional structural property: this matrix can be represented as a conic combination of cut matrices in a certain normal form. The other matrix is a conic combination of a monotone anti-Monge matrix and a down-benevolent Toeplitz matrix. We consider the recognition problem for the special class of Robinson matrices mentioned above and show that it can be solved in polynomial time.

We introduce a new binary quadratic program that subsumes the well known quadratic assignment problem. This problem is shown to be NP-hard when some associated parameters are restricted to simple values but solvable in polynomial time when some other parameter values are restricted. Three different neighborhood structures are introduced. A best solution in all these neighborhoods can be identified in polynomial time even though two of these neighborhoods are of exponential size. Different local search algorithms and their enhancements using tabu search are developed using these neighborhoods. Experimental analysis show that two hybrid algorithms obtained by combining these neighborhoods in specific ways yield results that are superior to the algorithms that use these neighborhoods separately. Extensive computational results and statistical analysis of the resulting data are presented.

Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. It is also a crucial component of many state-of-the-art algorithms for such problems. However, PLS may be not very effective when terminated before completion. In other words, PLS has poor anytime behavior. In this paper, we study the effect that various PLS algorithmic components have on its anytime behavior. We show that the anytime behavior of PLS can be greatly improved by using alternative algorithmic components. We also propose Dynagrid, a dynamic discretization of the objective space that helps PLS to converge faster to a good approximation of the Pareto front and continue to improve it if more time is available. We perform a detailed empirical evaluation of the new proposals on the bi-objective traveling salesman problem and the bi-objective quadratic assignment problem. Our results demonstrate that the new PLS variants not only have significantly better anytime behavior than the original PLS, but also may obtain better results for longer computation time or upon completion., SCOPUS: ar.j, info:eu-repo/semantics/published

We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented.

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of 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 in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.

Two criteria in a combinatorial problem are often combined in a weighted sum objective using a weighting parameter between 0 and 1. For special problem types, e.g., when one of the criteria is a bottleneck value, efficient algorithms are known that solve for a given value of the weighting parameter. We transform the underlying enumeration method into a parametric algorithm solving simultaneously for all values of the weighting parameter. Efficient implementations are presented for combinatorial problems with criteria as balanced optimization, min–sum with min–max, and min–sum with balanced optimization, considering the spanning tree, the linear assignment and the single machine scheduling problem. Further the new algorithmic scheme can easily incorporate a trade-off of the criteria by means of penalty functions, again without consequences for the algorithm and its complexity order.

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.

Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of optimization is impressive, since problem classes both in the continuous and discrete world, as well as both deterministic and stochastic models are covered. Copositivity appears in local and global optimality conditions for quadratic optimization, but can also yield tighter bounds for NP-hard combinatorial optimization problems. Here some of the recent success stories are told, along with principles, algorithms and applications.

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities.

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.

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem’s solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64. We present an exact solution method based upon a reformulation linearization technique that is one of the best available for solving the quadratic assignment problem (QAP). Our current exact algorithm is useful for Q3AP instances of size 13 or smaller. We also investigate four stochastic local search algorithms that provide optimum or near optimum solutions for large and difficult QAP instances and adapt them for solving the Q3AP. The results of our experiments make it possible to get good solutions to signal mapping problems of size 8 and 16.

This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0–1 linear representations that result from a reformulation–linearization technique (rlt). The rlt provides different “levels” of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances.

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.

Iterated local search (ILS) is a simple and powerful stochastic local search method. This article presents and analyzes the application of ILS to the quadratic assignment problem (QAP). We justify the potential usefulness of an ILS approach to this problem by an analysis of the QAP search space. However, an analysis of the run-time behavior of a basic ILS algorithm reveals a stagnation behavior which strongly compromises its performance. To avoid this stagnation behavior, we enhance the ILS algorithm using acceptance criteria that allow moves to worse local optima and we propose population-based ILS extensions. An experimental evaluation of the enhanced ILS algorithms shows their excellent performance when compared to other state-of-the-art algorithms for the QAP.

The Three-Index Assignment Problem (AP3) is well-known problem which has been shown to be NP -hard. This problem has been studied extensively, and many exact and heuristic methods have been proposed to solve it. Inspired by the classical assignment problem, we propose a new local search heuristic which solves the problem by simplifying it to the classical assignment problem. We further hybridize our heuristic with the genetic algorithm (GA). Extensive experimental results indicate that our hybrid method is superior to all previous heuristic methods including those proposed by Balas and Saltzman [Operations Research 39 (1991) 150–161], Crama and Spieksma [European Journal of Operational Research 60 (1992) 273–279], Burkard et al. [Discrete Applied Mathematics 65 (1996) 123–169], and Aiex et al. [GRASP with path relinking for the three-index assignment problem, Technical report, INFORMS Journal on Computing, in press. Available from: ].

This paper studies the performance of two stochastic local search algorithms for the biobjective Quadratic Assignment Problem with different degrees of correlation between the flow matrices. The two algorithms follow two fundamentally different ways of tackling multiobjective combinatorial optimization problems. The first is based on the component-wise ordering of the objective value vectors of neighboring solutions, while the second is based on different scalarizations of the objective function vector. Our experimental results suggest that the performance of the algorithms with respect to solution quality and computation time depends strongly on the correlation between the flow matrices. In addition, some variants of these stochastic local search algorithms obtain very good solutions in short computation time.

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and supply chains. The problem has been studied since the late 1960s, and computer codes for practical applications emerged in the early 1970s. We propose a new algorithm for this problem that proves to be more effective than previously existing methods. The algorithm features a path relinking approach, which is a mechanism for generating new solutions by combining two or more reference solutions. It also features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. Computational comparisons on benchmark instances show that the method is not only effective in general, but is especially effective for types D and E instances, which are known to be very difficult.

In this paper we propose to extend the concentric tabu search for the quadratic assignment problem to include more permissible moves. Two extensions are suggested and tested. The computational comparisons with existing hybrid genetic algorithms provide comparable solutions to the best available algorithms.

The k-cardinality Linear Assignment Problem (k-LAP) with k a given integer is a generalization of the linear assignment problem: one wants to assign k rows (a free choice out of more rows) to k columns (a free choice out of more columns) minimizing the sum of the corresponding costs. For this polynomially solvable problem special algorithms are known based on transformation to min-cost flow or on shortest augmenting paths. We describe a transformation that enables to solve the k-LAP by any standard linear assignment algorithm. The transformation can be modified to solve the group assignment problem as a standard problem. Computational results for random test instances up to size n=500 with various k-values and randomly drawn cost coefficients show that the transformation approach is suited to solve the k-LAP within short computer times on a standard personal computer.

In this paper the network structure of basic solutions to the quadratic assignment problem (QAP) is revisited. The concept of a relative local star minimum is introduced. Results characterizing a relative local star minimum are obtained. Then an extreme point algorithm for QAP is proposed.

Consider an assignment problem in which persons are qualified for a subset of the jobs; assume the persons to belong to given seniority classes. Seniority constraints impose that the solution is such that no free person can be given a job unless an assigned person with the same or higher seniority becomes free. Similarly, jobs can belong to priority classes for which priority constraints must hold. It is shown that the assignment problem with both types of constraints can be solved by successively reoptimizing a (rectangular) linear assignment problem of increasing size. The related complexity is lower than for a known coefficient scaling approach. A further advantage of this approach is that it is easy to modify to solve the problem under the bottleneck criterion.

A machine-cell itself can be treated as a machine, and the location of such a cell in a linear line configuration reflects an analogy to the machine location problem. Thus, the problem addressed here is a one-dimensional equidistant machine-cell location problem that considers jobs with sequenced-operations, and the number of machine-cells equals the number of locations that are equally spaced in a linear layout. It is always desirable to achieve a cell assignment that minimizes the total inter-cell flows and, thus, the total inter-cell flow costs. This assignment problem can be formulated as a quadratic assignment problem the optimal solution to which is usually prohibitive since it is a non-deterministically polynomial hard problem, and a heuristic procedure is justifiably called for in this research. Many of the investigations involved in seeking an improved location assignment in heuristics are repeated from one search to another. Each branch of the search requires re-computation of all inter-cell flows, though only some of them have been changed from the previous one. Such a search mechanism requires considerable computation time, thus making the algorithm inefficient. This problem can be overcome by directionally decomposing the inter-cell flows and incrementally computing them. Based on the directional decomposition of these flows, a directional search is implemented in the heuristic in order to reduce the repetitiveness occurring in the traditional search. Both the partitioning procedure and the directional decomposition heuristic proposed here are demonstrated through examples, and the performance measures indicate the superiority of the heuristic over the existing methods.

In this paper we propose a new method to solve biobjective combinatorial optimization problems of the max-ordering type. The method is based on the two-phases method and ranking algorithms to efficiently construct K-best solutions for the underlying (single objective) combinatorial problem. We show that the method overcomes some of the difficulties of procedures proposed earlier. We illustrate this by an example and discuss the difficulties in extending it to more than two objectives.

This paper deals with a combinatorial optimization problem that arises in the design of a semi-automatic system for cutting leather skins called the laser multi-scanner problem (LMSP). The problem occurs in the first part of the cutting process: the parts to be cut are placed on the cutting board by using a new technique, the so-called `lasernest'; the outlines of the pieces are projected onto the board by several laser rays. The optimization goal is to assign the pieces to the laser rays such that the maximum length of a laser route is minimal. This can be modelled as a new variant of a vehicle routing problem. Due to severe time restrictions we are only interested in fast heuristic solutions. We construct feasible solutions by opening heuristics, namely, insertion algorithms and greedy variants. In a second step we improve the solutions using local search based on arc exchanges. We evaluate the quality of solutions by lower bounds which are derived from combinatorial and LP-relaxations. Thereby, we examine directed Q -forests on a multi-digraph which have matroid structure. Finally, we present some computational results on real-world data.

An assignment heuristic is developed for allocating cross-trained workers to multiple departments at the beginning of a shift. The cross-trained workers may have different levels of qualification in different departments. With non-linear departmental objective functions and binary decision variables, the problem's formulation represents a variant of the generalized assignment problem, whose difficulty is well known. The new assignment heuristic is based on a linear assignment approximation that takes advantage of the special structure of the cross-utilization problem. It is shown that this assignment heuristic is superior to a classical Lagrangian heuristic and a simplistic Greedy approach. Experimental evaluations are facilitated by the development of a technique that provides tight bounds for the problem. Based on a standard measure of performance, assignment heuristic solutions average within 0.09% of upper bounds across a variety of problem characteristics.

This paper considers the generalized assignment problem (GAP). It is a well-known NP-hard combinatorial optimization problem that is interesting in itself and also appears as a subproblem in other problems of practical importance. A Tabu search heuristic for the GAP is proposed. The algorithm uses recent and medium-term memory to dynamically adjust the weight of the penalty incurred for violating feasibility. The most distinctive features of the proposed algorithm are its simplicity and its flexibility. These two characteristics result in an algorithm that, compared to other well-known heuristic procedures, provides good quality solutions in competitive computational times. Computational experiments have been performed in order to evaluate the behavior of the proposed algorithm.

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.

The simultaneous assignment problem is formulated as an extension to the assignment problem. The problem is proved NP -hard. We evaluate its lower bound and present some approximate algorithms. Also we introduce the pegging test to this problem and show that this remarkably reduces the size of the original problem. Combining these we give an algorithm to solve the problem to optimality, and through numerical tests analyze the behavior of the developed algorithms. Randomly generated test problems with up to 48 000 variables are solved in less than a few minutes.

Focusing on the generation mechanism of random permutation solutions, this paper investigates the application of the Simulated Annealing (SA) algorithm to the combinatorial optimisation problems with permutation property. Six types of perturbation scheme for generating random permutation solutions are introduced. They are proved to satisfy the asymptotical convergence requirements. The results of experimental evaluations on Traveling Salesman Problem (TSP), Flow-shop Scheduling Problem (FSP), and Quadratic Assignment Problem (QAP) reveal that the efficiencies of the perturbation schemes are different in searching a solution space. By adopting a proper perturbation scheme, the SA algorithm has shown to produce very efficient solutions to different combinatorial optimisation problems with permutation property.

Production planning problems frequently involve the assignment of jobs or operations to machines. The simplest model of this problem is the well known assignment problem (AP). However, due to simplifying assumptions this model does not provide implementable solutions for many actual production planning problems. Extensions of the simple assignment model known as the generalized assignment problem (GAP) and the multi-resource generalized assignment problem (MRGAP) have been developed to overcome this difficulty. This paper presents an extension of the (MRGAP) to allow splitting individual batches across multiple machines, while considering the effect of setup times and setup costs. The extension is important for many actual production planning problems, including ones in the injection molding industry and in the metal cutting industry. We formulate models which are logical extensions of previous models which ignored batch splitting for the problem we address. We then give different formulations and suggest adaptations of a genetic algorithm (GA) and simulated annealing (SA). A systematic evaluation of these algorithms, as well as a Lagrangian relaxation (LR) approach, is presented.

This paper presents a new branch-and-bound algorithm for solving the quadratic assignment problem (QAP). The algorithm is based on a dual procedure (DP) similar to the Hungarian method for solving the linear assignment problem. Our DP solves the QAP in certain cases, i.e., for some small problems (N< 7) and for numerous larger problems (7≤ N ≤16) that arise as sub-problems of a larger QAP such as the Nugent 20. The DP, however, does not guarantee a solution. It is used in our algorithm to calculate lower bounds on solutions to the QAP. As a result of a number of recently developed improvements, the DP produces lower bounds that are as tight as any which might be useful in a branch-and-bound algorithm. These are produced relatively cheaply, especially on larger problems. Experimental results show that the computational complexity of our algorithm is lower than known methods, and that its actual runtime is significantly shorter than the best known algorithms for QAPLIB test instances of size 16 through 22. Our method has the potential for being improved and therefore can be expected to aid in solving even larger problems.

Lower bounds for the frequency assignment problem can be found from maximal cliques and subgraphs related to cliques. In this paper we show that for many types of problem optimal assignments can be found by a process of assigning these subgraphs first, fixing the assignment and then extending the assignment to the full problem. We demonstrate the advantages of the method for some typical examples. In particular we give the first optimal assignments of several variants of the “Philadelphia” problems. These problems have been used by several authors to assess assignment methods and lower bounds.

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.

A solution methodology producting exact solutions to the manufacturing systems cell formation problem is presented. A distance matrix representing the closeness between pairs of machines with regard to the parts they process is taken into account. The proposed approach is an optimal tree search method which empoys two different bounds; a classical bound for the Quadratic Assignment Problem and a recently proposed one for the Quadratic Transportation Problem, as well as a new heuristic for the cell formation problem. A special tree search was designed in order to reduce the size of the tree, minimize the computational effort required in time consuming calculations and exploit symmetries of the problem. Computational results indicate that the proposed algorithm is very efficient in generating optimal solutions at low computational cost.

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.

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O ( N 2( α + β −1) ) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.

We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented.

A novel representation is described that models some important NP-hard problems, such as the propositional satisfiability problem (SAT), the Traveling Salesperson Problem (TSP), the Quadratic Assignment Problem (QAP), and the Minimal Set Covering Problem (MSCP) by means of only two types of constraints: ‘choice constraints’ and ‘exclusion constraints’. In its main section the paper presents an approach for solving an m-CNF-SAT problem (Conjunctive Normal Form Satisfaction: n variables, p clauses, clause length m) by integer programming. The approach is unconventional, because 2n distinct 0–1 variables are used for each clause of the m-CNF-SAT problem. The constraint matrix A forces that for every clause exactly one 0–1 variable is set equal to 1 (choice constraint), and no two 0–1 variables, representing a literal and its complement, are both set equal to 1 (exclusion constraints). The particular m-CNF-SAT instance is coded in a cost vector, which serves for maximization of the number of satisfied clauses. The paper presents a modification of the Simplex for solving the obtained integer program. A main theorem of the paper is that this algorithm always finds a 0–1 integer solution. A solution of the integer program corresponds to a solution of the m-CNF-SAT and vice versa. The results of significant experimental tests are reported, and the procedure is compared to other approaches. The same modelling technique is then used for the Traveling Salesperson Problem, for the Minimal Set Covering, and for the Quadratic Assignment Problem: it is shown that a uniform approach is thus useful.

This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.

The Quadratic Semi-Assignment Problem (QSAP) models a large variety of practical applications. In the present note we will consider a particular class of QSAP that can be solved by determining the maximum cost flow on a network. This class of problems arises in schedule synchronization and in transportation.

Local search methods for combinatorial optimization make a series of steps, at each stage improving the current solution by moving to a neighbouring solution. This is usually done by considering the neighbouring solutions one at a time and moving to the first one which gives an improvement (a first-improving method). In this paper we consider whether there are circumstances in which some other strategy will have better performance. In exploring this question we begin by giving a theoretical treatment of a simple model with random objective values at each solution point. We carry out some experiments on the Travelling Salesman Problem and the Quadratic Assignment Problem using varying values of a spread parameter, k . The value of k corresponds to the number of improving solutions looked at before making a move. We also make some conjectures relating the overall performance of the local search method to the average number of solutions which are evaluated before a local minimum is reached.

We present a new research domain in Operational Research, probabilistic combinatorial optimization problems. We survey and comment a number of results, and we discuss several problems dealing with this domain as well as future research issues.

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). As for any hard optimization problem also for BiQAP, a reasonable effort to cope with the problem is trying to derive heuristics which solve it suboptimally and which, possibly, yield a good trade off between the solution quality and the time and memory requirements. In this paper we describe several heuristics for BiQAPs, in particular pair exchange algorithms (improvement methods) and variants of simulated annealing and taboo search. We implement these heuristics as C codes and analyze their performances.

We propose a new parallel Branch and Bound algorithm for the Quadratic Assignment Problem, which is a Combinatorial Optimization problem known to be very hard to solve exactly. An original method to distribute work to processors using the notion of Feeding Tree is presented. When adequately used, it allows to reduce memory contention and load unbalance. Therefore, a linear speed-up in the number of processors is reached on a shared memory multiprocessor, the Cray 2 and the optimality of solutions for famous problems of size less than 20 (Nugent 16, Elshafei 19, Scriabin-Vergin 20,…) is proved by this program. The implementation analysis shows that these results are more than an improvement due to hardware evolution and confirms the usefulness of our parallel Branch and Bound algorithm for larger Quadratic Assignment Problems.

Let E be a finite set, and F be a family of subsets of E . For each element e ϵ E , p weights c e i , i = 1, 2,…, p are prescribed. Then the minmax combinatorial optimization problem is to Minimize SϵF Maximum 1≤ i ≤ p Σ eϵS { c e i }. Several special cases of this general problem, viz. 3-partition, makespan minimization problem, bandwidth minimization in matrices and graphs, categorized assignment problem, etc., have been studied in literature. In this paper we propose exact and heuristic methods to solve the general problem. Our algorithms also give some new insights into the application of subgradient optimization in solving the Lagrangean dual of combinatorial problems when the Lagrange multipliers are required to satisfy additional constraints. Encouraging computational results are also reported.

This paper presents a result of transforming a class of non-convex programs into parametric programs. Parametric linear programming algorithms are then developed to solve several special cases of the quadratic assignment problem (QAP). Lower and upper bounds of the parameters are derived to further accelerate the parameter search. Numerical experiments are conducted to show the efficiency of the algorithm.

Facility layout and location problems with stochastic congestion in the traffic circulation system have been studied in a previous paper. In this paper, we present a heuristic algorithm to solve these complex problems. With its straight forward approach, the algorithm can solve large-scale Quadratic Assignment Problems with reasonable computing times and efficient performance. Computational experience for solving many test examples is also presented.

This work compares the effectiveness of eight evolutionary heuristic algorithms applied to the Quadratic Assignment Problem (QAP), reputedly one of the most difficult combinatorial optimization problems. QAP is merely used as a carrier for the comparison: we do not attempt to compare any heuristics with solving algorithms specific for it. Results are given, both with respect to the best result achieved by each algorithm in a limited time span and to its speed of convergence to that result.