81 results on '"QUADRATIC assignment problem"'
Search Results
2. The linearization problem of a binary quadratic problem and its applications.
- Author
-
Hu, Hao and Sotirov, Renata
- Subjects
- *
DIRECTED acyclic graphs , *ALGORITHMS , *QUADRATIC assignment problem - Abstract
We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. Each linearization-based bound requires a set of linearizable matrices as an input. We prove that the Generalized Gilmore–Lawler bounding scheme for binary quadratic problems provides linearization-based bounds. Moreover, we show that the bound obtained from the first level reformulation linearization technique is also a type of linearization-based bound, which enables us to provide a comparison among mentioned bounds. However, the strongest linearization-based bound is the one that uses the full characterization of the set of linearizable matrices. We also present a polynomial-time algorithm for the linearization problem of the quadratic shortest path problem on directed acyclic graphs. Our algorithm gives a complete characterization of the set of linearizable matrices for the quadratic shortest path problem. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
3. Biologically Inspired Parent Selection in Genetic Algorithms.
- Author
-
Drezner, Zvi and Drezner, Taly Dawn
- Subjects
- *
GENETIC algorithms , *QUADRATIC assignment problem - Abstract
In this paper we suggest a new rule for parent selection in genetic algorithms inspired by natural evolutionary processes. The new rule is simple to implement in any genetic or hybrid genetic algorithm. We also review some biological principles that inspire genetic algorithms and their extensions. The new rule is tested on the planar p-median problem, also termed the location–allocation problem or the multi-source Weber problem, and the quadratic assignment problem. The genetic algorithm incorporating the new rule provided better results without increasing the computing time including five new best known solutions to well researched problem instances. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
4. Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints.
- Author
-
Guignard, Monique
- Subjects
- *
QUADRATIC assignment problem , *KNAPSACK problems , *ASSIGNMENT problems (Programming) , *RELAXATION for health - Abstract
The Reformulation Linearization Technique (RLT) of Sherali and Adams (Manag Sci 32(10):1274–1290, 1986; SIAM J Discrete Math 3(3):411–430, 1990), when applied to a pure 0–1 quadratic optimization problem with linear constraints (P), constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes. These provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. Their size and their complexity increase drastically with k. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature. We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved as a 0–1 rather than a continuous problem, one may be able to obtain 0–1 RLT1 bounds of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. If one actually decomposes the Lagrangean relaxation model, this two-step procedure, reformulation plus decomposed Lagrangean relaxation, will produce linear 0–1 Lagrangean subproblems with a dimension no larger than that of the original model. We first present numerical results for the Crossdock Door Assignment Problem, a special case of the Generalized Quadratic Assignment Problem. These show that just solving one Lagrangean relaxation problem in 0–1 variables produces a bound close to or better than the standard continuous RLT2 bound (when available) but much faster, especially for larger instances, even if one does not actually decompose the Lagrangean problem. We then present numerical results for the 0–1 quadratic knapsack problem, for which no RLT2 bounds are available to our knowledge, but we show that solving an initial Lagrangean relaxation of a specific 0–1 RLT1 decomposable model drastically improves the quality of the bounds. In both cases, solving the fully decomposed rather than the decomposable Lagrangean problem to optimality will make it feasible to compute such bounds for instances much too large for computing the standard continuous RLT2 bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
5. A Benders decomposition approach to product location in carousel storage systems.
- Author
-
Vickson, Raymond G., Hassini, Elkafi, and Azad, Nader
- Subjects
- *
QUADRATIC assignment problem , *STORAGE - Abstract
In this paper we discuss the problem of locating items within carousel bins in order to minimize the average carousel rotational distance per retrieval. We consider two cases: (1) a single two-dimensional carousel and (2) a group of two one-dimensional carousels. The corresponding problems are formulated as mixed-integer programs. In the second problem we apply concepts from Markovian performance evaluation methods to write the objective functions in a simple linear form. We also define a set of uniqueness constraints that significantly reduces the size of the solution feasibility space. We then apply Benders decomposition algorithm to solve both problems. We develop a closed form solution for the dual subprobem and present numerical results to show the efficiency of the proposed solution methodology. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
6. The multi-stripe travelling salesman problem.
- Author
-
Çela, Eranda, Deineko, Vladimir, and Woeginger, Gerhard
- Subjects
- *
SELLING , *TRAVEL , *CITIES & towns , *MATRICES (Mathematics) , *MATHEMATICS theorems - Abstract
In the classical Travelling Salesman Problem (TSP), the objective function sums the costs for travelling from one city to the next city along the tour. In the q-stripe TSP with $$q\ge 1$$ , the objective function sums the costs for travelling from one city to each of the next q cities in the tour. The resulting q-stripe TSP generalizes the TSP and forms a special case of the quadratic assignment problem. We analyze the computational complexity of the q-stripe TSP for various classes of specially structured distance matrices. We derive NP-hardness results as well as polynomially solvable cases. One of our main results generalizes a well-known theorem of Kalmanson from the classical TSP to the q-stripe TSP. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
7. Experimental analysis of crossover and mutation operators on the quadratic assignment problem.
- Author
-
Ahmed, Zakir
- Subjects
- *
GENETIC algorithms , *CHROMOSOMES , *GENETIC mutation , *GENES , *QUADRATIC assignment problem - Abstract
In genetic algorithms crossover is the most important operator where pair of chromosomes and crossover site along their common length are selected randomly. Then the information after the crossover site of the parent chromosomes is swapped. On the other hand, mutation operator randomly alters some genes of a chromosome, and thus diversifies the search space. We consider three crossover and ten mutation operators for the genetic algorithms which are then compared for the quadratic assignment problem on some benchmark QAPLIB instances. The experimental study shows the effectiveness of the sequential constructive crossover and the adaptive mutation operators for the problem. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
8. Biologically Inspired Parent Selection in Genetic Algorithms
- Author
-
Zvi Drezner and Taly Dawn Drezner
- Subjects
021103 operations research ,Hybrid genetic algorithms ,business.industry ,Computer science ,Quadratic assignment problem ,Computer Science::Neural and Evolutionary Computation ,0211 other engineering and technologies ,General Decision Sciences ,02 engineering and technology ,Weber problem ,Management Science and Operations Research ,Simple (abstract algebra) ,Genetic algorithm ,Theory of computation ,Artificial intelligence ,business ,Selection (genetic algorithm) - Abstract
In this paper we suggest a new rule for parent selection in genetic algorithms inspired by natural evolutionary processes. The new rule is simple to implement in any genetic or hybrid genetic algorithm. We also review some biological principles that inspire genetic algorithms and their extensions. The new rule is tested on the planar p-median problem, also termed the location–allocation problem or the multi-source Weber problem, and the quadratic assignment problem. The genetic algorithm incorporating the new rule provided better results without increasing the computing time including five new best known solutions to well researched problem instances.
- Published
- 2019
9. A Benders decomposition approach to product location in carousel storage systems
- Author
-
Elkafi Hassini, Nader Azad, and Raymond G. Vickson
- Subjects
Mathematical optimization ,021103 operations research ,Quadratic assignment problem ,Computer science ,0211 other engineering and technologies ,General Decision Sciences ,Markov process ,02 engineering and technology ,Management Science and Operations Research ,Dual (category theory) ,symbols.namesake ,Linear form ,Product (mathematics) ,Set of uniqueness ,Theory of computation ,symbols ,Closed-form expression - Abstract
In this paper we discuss the problem of locating items within carousel bins in order to minimize the average carousel rotational distance per retrieval. We consider two cases: (1) a single two-dimensional carousel and (2) a group of two one-dimensional carousels. The corresponding problems are formulated as mixed-integer programs. In the second problem we apply concepts from Markovian performance evaluation methods to write the objective functions in a simple linear form. We also define a set of uniqueness constraints that significantly reduces the size of the solution feasibility space. We then apply Benders decomposition algorithm to solve both problems. We develop a closed form solution for the dual subprobem and present numerical results to show the efficiency of the proposed solution methodology.
- Published
- 2019
10. Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints
- Author
-
Monique Guignard
- Subjects
021103 operations research ,Optimization problem ,Quadratic assignment problem ,0211 other engineering and technologies ,General Decision Sciences ,02 engineering and technology ,Management Science and Operations Research ,Quadratic equation ,Linearization ,Theory of computation ,Applied mathematics ,Quadratic programming ,Relaxation (approximation) ,Assignment problem ,Mathematics - Abstract
The Reformulation Linearization Technique (RLT) of Sherali and Adams (Manag Sci 32(10):1274–1290, 1986; SIAM J Discrete Math 3(3):411–430, 1990), when applied to a pure 0–1 quadratic optimization problem with linear constraints (P), constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes. These provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. Their size and their complexity increase drastically with k. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature. We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved as a 0–1 rather than a continuous problem, one may be able to obtain 0–1 RLT1 bounds of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. If one actually decomposes the Lagrangean relaxation model, this two-step procedure, reformulation plus decomposed Lagrangean relaxation, will produce linear 0–1 Lagrangean subproblems with a dimension no larger than that of the original model. We first present numerical results for the Crossdock Door Assignment Problem, a special case of the Generalized Quadratic Assignment Problem. These show that just solving one Lagrangean relaxation problem in 0–1 variables produces a bound close to or better than the standard continuous RLT2 bound (when available) but much faster, especially for larger instances, even if one does not actually decompose the Lagrangean problem. We then present numerical results for the 0–1 quadratic knapsack problem, for which no RLT2 bounds are available to our knowledge, but we show that solving an initial Lagrangean relaxation of a specific 0–1 RLT1 decomposable model drastically improves the quality of the bounds. In both cases, solving the fully decomposed rather than the decomposable Lagrangean problem to optimality will make it feasible to compute such bounds for instances much too large for computing the standard continuous RLT2 bounds.
- Published
- 2018
11. Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers.
- Author
-
Zhang, Huizhen, Beltran-Royo, Cesar, and Ma, Liang
- Subjects
- *
QUADRATIC assignment problem , *COMPUTER programming , *INTEGERS , *LINEAR programming , *MATHEMATICAL programming , *MATHEMATICAL reformulation - Abstract
The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearizations are tight, but rarely exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation (Eur. J. Oper. Res. 2(3):204-211, ) is the smallest of these linearizations, but very weak. In this paper, we analyze how the Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As shown in our numerical experiments, these tightened formulations remain small but computationally effective to solve the QAP by means of general purpose MILP solvers. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
12. To lay out or not to lay out?
- Author
-
Niroomand, Sadegh, Takács, Szabolcs, and Vizvári, Béla
- Subjects
- *
QUADRATIC assignment problem , *INTEGER programming , *ARTIFICIAL intelligence , *TRAVELING salesman problem , *SCALING laws (Statistical physics) - Abstract
The Quadratic Assignment Problem (QAP) is known as one of the most difficult problems within combinatorial optimization. It is used to model many practical problems including different layout problems. The main topic of this paper is to provide methods to check whether a particular instance of the QAP is a layout problem. An instance is a layout problem if the distances of the objects can be reconstructed on the plane and/or in the 3-dimensional space. A new mixed integer programming model is suggested for the case if the distances of the objects are supposed to be rectilinear distances. If the distances are Euclidean distances then the use of the well-known Multi-Dimensional Scaling (MDS) method of statistics is suggested for reconstruction purposes. The well-known difficulty of QAP makes it a popular and suitable experimental field for many algorithmic ideas including artificial intelligence methods. These types of results are published sometimes as layout problems. The methods of reconstruction can be used to decide whether the topic of a paper is layout or only general QAP. The issue what the OR community should expect from AI based algorithms, is also addressed. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
13. Discrete optimization: An Austrian view.
- Author
-
Burkard, Rainer E.
- Subjects
- *
MATHEMATICAL optimization , *QUADRATIC assignment problem , *COMBINATORIAL optimization , *MATHEMATICAL analysis , *OPERATIONS research - Abstract
The author offers his views on discrete optimization. According to him, the obvious analogies between quadratic assignment problems with a sum objective and quadratic assignment problems with a bottleneck objective led to an investigation on the common mathematical background of both problems. Some of the factors that makes the optimization attractive are the links to other mathematical areas like algebra and numerical analysis, geometry and combinatorics.
- Published
- 2007
- Full Text
- View/download PDF
14. Dual ascent: variations of a theme.
- Author
-
Krarup, Jakob
- Subjects
- *
OPERATIONS research , *COMBINATORIAL optimization , *COMBINATORICS , *MATHEMATICAL programming , *QUADRATIC assignment problem - Abstract
The author relates his experience in working in operations research. He notes that a substantial proportion of Combinatorial Optimisation Problems are essentially pure or mixed 0-1 programming problems with a linear objective function and linear constraints. The author also stresses that one of the computationally hardest combinatorial optimisation problem is the Quadratic Assignment Problem.
- Published
- 2007
- Full Text
- View/download PDF
15. Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods.
- Author
-
Drezner, Zvi, Hahn, Peter, and Taillard, Éeric
- Subjects
- *
QUADRATIC assignment problem , *COMPUTER programming , *HEURISTIC , *ARTIFICIAL intelligence , *COMBINATORIAL optimization , *METHODOLOGY - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
16. An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem.
- Author
-
Kochenberger, Gary, Glover, Fred, Alidaee, Bahram, and Rego, Cesar
- Subjects
- *
QUADRATIC programming , *BINARY number system , *COMPUTER arithmetic , *VERTEX operator algebras , *COMBINATORIAL optimization , *GENETIC algorithms , *QUADRATIC assignment problem , *MATHEMATICAL optimization - Abstract
The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
17. On A Special Case of the Quadratic Assignment Problem with an Application to Storage-and-Retrieval Devices.
- Author
-
Polak, George G.
- Subjects
- *
INFORMATION storage & retrieval systems , *COMPUTER peripherals , *QUADRATIC assignment problem , *ELECTRONIC equipment , *ROBOTS , *MINIATURE electronic equipment - Abstract
In a storage-and-retrieval device, items are retrieved on demand from a storage bank by a picking mechanism. Many varieties of these robotic devices are in use in manufacturing, logistics and computer peripherals. In printed circuit board manufacturing, storage-and-retrieval is intertwined with component placement and product clustering. Under certain circumstances, the problem of assigning items by type to storage slots to minimize the expected retrieval time is a quadratic assignment problem. Although such models are very difficult to solve to optimality, an important special case considered here admits an easy solution, namely, the well known “organ pipe” arrangement of items. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
18. Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem.
- Author
-
Palubeckis, Gintaras
- Subjects
- *
MATHEMATICAL optimization , *BINARY number system , *QUADRATIC assignment problem , *HEURISTIC , *COMBINATORIAL optimization , *MATHEMATICAL analysis - Abstract
This paper describes and experimentally compares five rather different multistart tabu search strategies for the unconstrained binary quadratic optimization problem: a random restart procedure, an application of a deterministic heuristic to specially constructed subproblems, an application of a randomized procedure to the full problem, a constructive procedure using tabu search adaptive memory, and an approach based on solving perturbed problems. In the solution improvement phase a modification of a standard tabu search implementation is used. A computational trick applied to this modification – mapping of the current solution to the zero vector – allowed to significantly reduce the time complexity of the search. Computational results are provided for the 25 largest problem instances from the OR-Library and, in addition, for the 18 randomly generated larger and more dense problems. For 9 instances from the OR-Library new best solutions were found. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
19. Applying an Extended Guided Local Search to the Quadratic Assignment Problem.
- Author
-
Mills, Patrick, Tsang, Edward, and Ford, John
- Subjects
HEURISTIC ,ARTIFICIAL intelligence ,QUADRATIC assignment problem ,COMBINATORIAL optimization ,ALGORITHMS - Abstract
In this paper, we show how an extended Guided Local Search (GLS) can be applied to the Quadratic Assignment Problem (QAP). GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. We present empirical results of applying several extended versions of GLS to the QAP, and show that these extensions can improve the range of parameter settings within which Guided Local Search performs well. Finally, we compare the results of running our extended GLS with some state of the art algorithms for the QAP. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
20. On the best search strategy in parallel branch-and-bound: Best-First Search versus Lazy Depth-First Search.
- Author
-
Clausen, Jens and Perregaard, Michael
- Subjects
ALGORITHMS ,FOUNDATIONS of arithmetic ,QUADRATIC assignment problem ,COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL optimization - Abstract
The Best-First Search strategy (BeFS) and the Depth-First Search strategy (DFS) are regarded as the prime strategies when solving combinatorial optimization problems by parallel Branch-and-Bound (B&3x0026;B) - BeFS because of efficiency with respect to the number of nodes explored, and DFS for reasons of space efficiency. We investigate the efficiency of both strategies experimentally, and two versions of each strategy are tested: In the first, a B&B iteration for a node consists of bounding followed by branching on the node if necessary. For the second, the order is reversed - first branching takes place, and then each child of the node is bounded and possibly fathomed. The first is called lazy, the second eager. The strategies are tested on the Quadratic Assignment Problem and the Job Shop Scheduling Problem. We use parallel codes developed specifically for the solution of the problem in question, and hence containing different heuristic rules and tests to speed up computation. In both cases, we start with an initial solution close to but not equal to the optimal solution. Surprisingly, the BeFS-based strategies turn out to be inferior to the DFS-based strategies, both in terms of running times and in terms of bound calculations performed. Furthermore, when tested in a sequential setting, DFS turns out to be still superior because pruning and evaluation tests are more effective in DFS due to the presence of better incumbents. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
21. Semidefinite relaxations for partitioning, assignment and ordering problems
- Author
-
Franz Rendl
- Subjects
Semidefinite programming ,Semidefinite embedding ,Mathematical optimization ,Quadratically constrained quadratic program ,021103 operations research ,Optimization problem ,L-reduction ,Linear programming ,Quadratic assignment problem ,0211 other engineering and technologies ,General Decision Sciences ,010103 numerical & computational mathematics ,02 engineering and technology ,Management Science and Operations Research ,01 natural sciences ,Theoretical Computer Science ,Management Information Systems ,Vector optimization ,Computational Theory and Mathematics ,Simplex algorithm ,0101 mathematics ,Assignment problem ,Conic optimization ,Large margin nearest neighbor ,Mathematics - Abstract
Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.
- Published
- 2015
22. Solution approaches to hub location problems.
- Author
-
Abdinnour-Helm, Sue and Venkataramanan, M. A.
- Subjects
COMBINATORIAL optimization ,NETWORK hubs ,QUADRATIC assignment problem ,GENETIC algorithms ,INTEGER programming ,NETWORK routers ,INTERNETWORKING devices - Abstract
The hub location problem involves a network of origins and destinations over which transport takes place. Any distribution system falls into this type of category. In this paper, we present a new quadratic integer formulation for the Uncapacitated Hub Location Problem (UHP), which is based on the idea of multi-commodity flows in networks. This new formulation lends itself well for using a branch-and-bound procedure to find optimal solutions. The branch-and-bound procedure is not implemented in a traditional fashion, where bounds are obtained by linearizing the objective function and relaxing the integrality constraints. Instead, a more sophisticated approach is used where bounds are obtained by employing the underlying network structure of the problem. In addition, an artificial intelligence-based technique (Genetic Search) is designed to find solutions quickly and efficiently. The two solution approaches assume that the number of hubs is a variable, each spoke is assigned to a single hub, and all hubs are interconnected. The model and the algorithm can be applied even when all the hubs are not directly linked. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
23. Locating sets of identical machines in a linear layout.
- Author
-
Sarker, Bhaba R., Wilhelm, Wilbert E., and Hogg, Gary L.
- Subjects
FLEXIBLE manufacturing systems ,BACKTRACK programming ,SIMULATION methods & models ,QUADRATIC assignment problem ,ASSIGNMENT problems (Programming) ,ALGORITHMS ,MATHEMATICAL optimization - Abstract
The assignment of M unique machines to M locations with the objective of minimizing the total machine-to-machine material transportation cost in a flow line may be formulated as a quadratic assignment problem (QAP). Instead of having M unique machines, if an application involves one or more sets of identical machines, the location problem becomes a tertiary assignment problem (TAP). Solving a large problem of this kind is extremely difficult because of its combinatorial nature. When machine-to-machine flow is fixed, the TAP may be specialized to a QAP for which the unique machine problem is a special case. Obtaining an optimum solution to this problem when M is large is also computationally intractable. However, this problem may be solved by identifying sets of identical machines which may be partitioned into individual, ‘unique’ machines. Properties of a special type of matrix called the amoebic matrix are used in the partitioned problems to provide approximate solutions, which are relabeled to prescribe a solution to the original problem. Results are demonstrated along with suggestions for further research. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
24. Lower bounds for the quadratic assignment problem.
- Author
-
Li, Y., Pardalos, P. M., Ramakrishnan, K. G., and Resende, M. G. C.
- Subjects
QUADRATIC assignment problem ,MATRICES (Mathematics) ,EIGENVALUES ,ALGORITHMS ,MATHEMATICAL programming - Abstract
We investigate the classical Gilmore–Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore–Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem. [ABSTRACT FROM AUTHOR]
- Published
- 1994
- Full Text
- View/download PDF
25. Massively parallel tabu search for the quadratic assignment problem.
- Author
-
Chakrapani, Jaishankar and Skorin-Kapov, Jadranka
- Subjects
HEURISTIC programming ,QUADRATIC assignment problem ,ALGORITHMS ,OPERATIONS research ,COMBINATORIAL optimization - Abstract
A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation uses n² processors, where n is the size of the problem. The elements of the algorithm, called Par_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time. [ABSTRACT FROM AUTHOR]
- Published
- 1993
- Full Text
- View/download PDF
26. THE PLANT LAYOUT PROBLEM IN AUTOMATED MANUFACTURING SYSTEMS.
- Author
-
Kouvelis, Panagiotis and Kiran, Ali S.
- Subjects
PLANT layout ,FACTORY design & construction ,PRODUCTION engineering ,QUADRATIC assignment problem ,COMBINATORIAL optimization ,FLEXIBLE manufacturing systems - Abstract
The plant layout problem is usually formulated as a quadratic assignment problem (QAP). In this paper, we incorporate the throughput related aspects of the automated manufacturing system into the layout problem. We modify the QAP formulation by explicitly considering the throughput requirements of automated manufacturing systems. Our formulation also incorporates the cost of keeping a certain number of pallet-fixtures in the system. The resulting modified quadratice assignment problem (MQAP) is presented. An optimal solution method for MQAP is developed and its computational performance is evaluated. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
27. Experimental analysis of crossover and mutation operators on the quadratic assignment problem
- Author
-
Zakir Hussain Ahmed
- Subjects
021103 operations research ,Quadratic assignment problem ,Crossover ,0211 other engineering and technologies ,General Decision Sciences ,02 engineering and technology ,Management Science and Operations Research ,Combinatorics ,Operator (computer programming) ,Adaptive mutation ,Mutation (genetic algorithm) ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,Edge recombination operator ,020201 artificial intelligence & image processing ,Mathematics - Abstract
In genetic algorithms crossover is the most important operator where pair of chromosomes and crossover site along their common length are selected randomly. Then the information after the crossover site of the parent chromosomes is swapped. On the other hand, mutation operator randomly alters some genes of a chromosome, and thus diversifies the search space. We consider three crossover and ten mutation operators for the genetic algorithms which are then compared for the quadratic assignment problem on some benchmark QAPLIB instances. The experimental study shows the effectiveness of the sequential constructive crossover and the adaptive mutation operators for the problem.
- Published
- 2015
28. Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers
- Author
-
Liang Ma, Huizhen Zhang, and Cesar Beltran-Royo
- Subjects
Mathematical optimization ,General purpose ,Linearization ,Quadratic assignment problem ,Theory of computation ,General Decision Sciences ,Management Science and Operations Research ,Integer programming ,Mathematics - Abstract
The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearizations are tight, but rarely exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation (Eur. J. Oper. Res. 2(3):204–211, 1978) is the smallest of these linearizations, but very weak. In this paper, we analyze how the Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As shown in our numerical experiments, these tightened formulations remain small but computationally effective to solve the QAP by means of general purpose MILP solvers.
- Published
- 2012
29. To lay out or not to lay out?
- Author
-
Sadegh Niroomand, Béla Vizvári, and Szabolcs Takács
- Subjects
Theoretical computer science ,Computer science ,Quadratic assignment problem ,Theory of computation ,Euclidean geometry ,General Decision Sciences ,Combinatorial optimization ,Management Science and Operations Research ,Space (commercial competition) ,Integer programming ,Algorithm ,Travelling salesman problem ,Field (computer science) - Abstract
The Quadratic Assignment Problem (QAP) is known as one of the most difficult problems within combinatorial optimization. It is used to model many practical problems including different layout problems. The main topic of this paper is to provide methods to check whether a particular instance of the QAP is a layout problem. An instance is a layout problem if the distances of the objects can be reconstructed on the plane and/or in the 3-dimensional space. A new mixed integer programming model is suggested for the case if the distances of the objects are supposed to be rectilinear distances. If the distances are Euclidean distances then the use of the well-known Multi-Dimensional Scaling (MDS) method of statistics is suggested for reconstruction purposes. The well-known difficulty of QAP makes it a popular and suitable experimental field for many algorithmic ideas including artificial intelligence methods. These types of results are published sometimes as layout problems. The methods of reconstruction can be used to decide whether the topic of a paper is layout or only general QAP. The issue what the OR community should expect from AI based algorithms, is also addressed.
- Published
- 2011
30. Solving the Rectangular assignment problem and applications
- Author
-
A. Volgenant, J. Bijsterbosch, and Operations Research
- Subjects
Decision Sciences(all) ,Linear bottleneck assignment problem ,Mathematical optimization ,Augmented assignment ,Quadratic assignment problem ,General Decision Sciences ,Management Science and Operations Research ,Scheduling (computing) ,Theory of computation ,Assignment problem ,Algorithm ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.
- Published
- 2010
31. The Multi-Story Space Assignment Problem
- Author
-
J. MacGregor Smith, Yi-Rong Zhu, and Peter M. Hahn
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Quadratic equation ,Branch and bound ,Quadratic assignment problem ,Theory of computation ,General Decision Sciences ,Management Science and Operations Research ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.
- Published
- 2008
32. A hybrid optimization approach to index tracking
- Author
-
Alberto Suárez and Rubén Ruiz-Torrubiano
- Subjects
Mathematical optimization ,Quadratically constrained quadratic program ,Fitness function ,Quadratic assignment problem ,business.industry ,Evolutionary algorithm ,General Decision Sciences ,Management Science and Operations Research ,Computer Science::Computational Engineering, Finance, and Science ,Genetic algorithm ,Theory of computation ,Economics ,Asset management ,Quadratic programming ,business - Abstract
Index tracking consists in reproducing the performance of a stock-market index by investing in a subset of the stocks included in the index. A hybrid strategy that combines an evolutionary algorithm with quadratic programming is designed to solve this NP-hard problem: Given a subset of assets, quadratic programming yields the optimal tracking portfolio that invests only in the selected assets. The combinatorial problem of identifying the appropriate assets is solved by a genetic algorithm that uses the output of the quadratic optimization as fitness function. This hybrid approach allows the identification of quasi-optimal tracking portfolios at a reduced computational cost.
- Published
- 2008
33. On local optima in multiobjective combinatorial optimization problems
- Author
-
Tommaso Schiavinotto, Thomas Stützle, and Luís Paquete
- Subjects
Extremal optimization ,Mathematical optimization ,Optimization problem ,Quadratic assignment problem ,Iterated local search ,General Decision Sciences ,Combinatorial search ,Combinatorial optimization ,Management Science and Operations Research ,Metaheuristic ,Tabu search ,Mathematics - Abstract
In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.
- Published
- 2007
34. Stability and accuracy functions in multicriteria linear combinatorial optimization problems
- Author
-
Marek Libura and Yury Nikulin
- Subjects
Continuous optimization ,Mathematical optimization ,Vector optimization ,Optimization problem ,Quadratic assignment problem ,Test functions for optimization ,Pareto principle ,General Decision Sciences ,Combinatorial optimization ,Management Science and Operations Research ,Multi-objective optimization ,Mathematics - Abstract
We consider a vector linear combinatorial optimization problem in which initial coefficients of objective functions are subject to perturbations. For Pareto and lexicographic principles of efficiency we introduce appropriate measures of the quality of a given feasible solution. These measures correspond to so-called stability and accuracy functions defined earlier for scalar optimization problems. Then we study properties of such functions and calculate the maximum norms of perturbations for which an efficient solution preserves the efficiency.
- Published
- 2006
35. A Combinatorial user optimal dynamic traffic assignment algorithm
- Author
-
Athanasios K. Ziliaskopoulos and S. Travis Waller
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Polynomial ,Computer science ,Heuristic ,Quadratic assignment problem ,General Decision Sciences ,Management Science and Operations Research ,Traffic flow ,Combinatorial optimization ,Queue ,Algorithm ,Generalized assignment problem ,Weapon target assignment problem - Abstract
This paper introduces a polynomial combinatorial optimization algorithm for the dynamic user optimal problem. The approach can efficiently solve single destination networks and can be potentially extended to heuristically solve multidestinational networks. In the model, traffic is propagated according to sound traffic flow theoretical models rather than link exit functions; thereby allowing link queue evolution to be modeled more precisely. The algorithm is designed, proven, implemented and computationally tested.
- Published
- 2006
36. Metaheuristics in Combinatorial Optimization
- Author
-
Michel Gendreau and Jean-Yves Potvin
- Subjects
Optimization problem ,Computer science ,Management science ,Quadratic assignment problem ,Theory of computation ,Vehicle routing problem ,General Decision Sciences ,Combinatorial optimization ,Management Science and Operations Research ,Metaheuristic ,Scheduling (computing) - Abstract
The emergence of metaheuristics for solving difficult combinatorial optimization problems is one of the most notable achievements of the last two decades in operations research. This paper provides an account of the most recent developments in the field and identifies some common issues and trends. Examples of applications are also reported for vehicle routing and scheduling problems.
- Published
- 2005
37. Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods
- Author
-
Éeric D. Taillard, Zvi Drezner, and Peter M. Hahn
- Subjects
Mathematical optimization ,Branch and bound ,Heuristic (computer science) ,Quadratic assignment problem ,Theory of computation ,General Decision Sciences ,Meta heuristic ,Fraction (mathematics) ,Management Science and Operations Research ,Metaheuristic ,Local search (constraint satisfaction) ,Mathematics - Abstract
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.
- Published
- 2005
38. An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem
- Author
-
Gary A. Kochenberger, César Rego, Fred Glover, and Bahram Alidaee
- Subjects
Greedy coloring ,Vertex (graph theory) ,Mathematical optimization ,Optimization problem ,Quadratic equation ,Quadratic assignment problem ,General Decision Sciences ,Combinatorial optimization ,Quadratic programming ,Graph coloring ,Management Science and Operations Research ,Mathematics - Abstract
The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.
- Published
- 2005
39. On the Convergence of the Cross-Entropy Method
- Author
-
L. Margolin
- Subjects
Mathematical optimization ,Cross entropy ,Optimization problem ,Quadratic assignment problem ,Theory of computation ,Convergence (routing) ,Cross-entropy method ,General Decision Sciences ,Combinatorial optimization ,Management Science and Operations Research ,Importance sampling ,Mathematics - Abstract
The cross-entropy method is a relatively new method for combinatorial optimization. The idea of this method came from the simulation field and then was successfully applied to different combinatorial optimization problems. The method consists of an iterative stochastic procedure that makes use of the importance sampling technique. In this paper we prove the asymptotical convergence of some modifications of the cross-entropy method.
- Published
- 2005
40. Some Fixed-Point Results for the Dynamic Assignment Problem
- Author
-
Michael Z. Spivey and Warren B. Powell
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Augmented assignment ,Quadratic assignment problem ,Theory of computation ,General Decision Sciences ,Management Science and Operations Research ,Fixed point ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
In previous work the authors consider the dynamic assignment problem, which involves solving sequences of assignment problems over time in the presence of uncertain information about the future. The algorithm proposed by the authors provides generally high-quality but non-optimal solutions. In this work, though, the authors prove that if the optimal solution to a dynamic assignment problem in one of two problem classes is unique, then the optimal solution is a fixed point under the algorithm.
- Published
- 2003
41. [Untitled]
- Author
-
Edward Tsang, John A. Ford, and Patrick Mills
- Subjects
Maxima and minima ,Range (mathematics) ,Mathematical optimization ,Quadratic assignment problem ,Iterated local search ,Theory of computation ,General Decision Sciences ,Guided Local Search ,Management Science and Operations Research ,Metaheuristic ,Local search (constraint satisfaction) ,Mathematics - Abstract
In this paper, we show how an extended Guided Local Search (GLS) can be applied to the Quadratic Assignment Problem (QAP). GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. We present empirical results of applying several extended versions of GLS to the QAP, and show that these extensions can improve the range of parameter settings within which Guided Local Search performs well. Finally, we compare the results of running our extended GLS with some state of the art algorithms for the QAP.
- Published
- 2003
42. [Untitled]
- Author
-
Riccardo Cambini and Claudio Sodini
- Subjects
Mathematical optimization ,Quadratically constrained quadratic program ,Periodic points of complex quadratic mappings ,Quadratic assignment problem ,General Decision Sciences ,Second-order cone programming ,Quadratic programming ,Management Science and Operations Research ,Solving quadratic equations with continued fractions ,Active set method ,Mathematics ,Sequential quadratic programming - Abstract
In this paper a particular quadratic minimum program, having a particular d.c. objective function, is studied. Some theoretical properties of the problem are stated and the existence of minimizers is characterized. A solution algorithm, based on the so called “optimal level solutions” approach, is finally proposed.
- Published
- 2002
43. [Untitled]
- Author
-
P. Jonker, Georg Still, and F. Twilt
- Subjects
Continuous optimization ,Quadratically constrained quadratic program ,Vector optimization ,Mathematical optimization ,Optimization problem ,L-reduction ,Quadratic assignment problem ,General Decision Sciences ,Stochastic optimization ,Quadratic programming ,Management Science and Operations Research ,Mathematics - Abstract
We consider families of optimization problems with quadratic object function and affine linear constraints, which depend smoothly on one real parameter. For a generic subclass of such problems only three different types of (generalized) critical points occur, whereas in the general case (of nonlinear one-parameter families of constrained optimization problems on Rn) five types are to be distinguished. We clarify the theoretical background of these phenomena and illustrate the underlying mechanism with simple examples.
- Published
- 2001
44. [Untitled]
- Author
-
Francesco Maffioli and Giulia Galbiati
- Subjects
Extremal optimization ,Mathematical optimization ,Optimization problem ,L-reduction ,Quadratic assignment problem ,Computer science ,Theory of computation ,Combinatorial optimization problem ,General Decision Sciences ,Combinatorial optimization ,Management Science and Operations Research ,Weapon target assignment problem - Published
- 2000
45. [Untitled]
- Author
-
Peter Csaszar, Thomas M. Tirpak, and Peter C. Nelson
- Subjects
Extremal optimization ,Mathematical optimization ,Incremental heuristic search ,Optimization problem ,Computational complexity theory ,business.industry ,Quadratic assignment problem ,Computer science ,General Decision Sciences ,Best-first search ,Management Science and Operations Research ,Tabu search ,Engineering optimization ,Search algorithm ,Derivative-free optimization ,Combinatorial search ,Beam search ,Combinatorial optimization ,Local search (optimization) ,Guided Local Search ,business ,Metaheuristic ,Hill climbing - Abstract
Combinatorial optimization represents a wide range of real-life manufacturing optimization problems. Due to the high computational complexity, and the usually high number of variables, the solution of these problems imposes considerable challenges. This paper presents a tabu search approach to a combinatorial optimization problem, in which the objective is to maximize the production throughput of a high-speed automated placement machine. Tabu search is a modern heuristic technique widely employed to cope with large search spaces, for which classical search methods would not provide satisfactory solutions in a reasonable amount of time. The developed TS strategies are tailored to address the different issues caused by the modular structure of the machine.
- Published
- 2000
46. [Untitled]
- Author
-
Wilbert E. Wilhelm, Bhaba R. Sarker, and Gary L. Hogg
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Quadratic assignment problem ,Backtracking ,Theory of computation ,General Decision Sciences ,Management Science and Operations Research ,Assignment problem ,Algorithm ,Generalized assignment problem ,Weapon target assignment problem ,Multi-commodity flow problem ,Mathematics - Abstract
The assignment of M unique machines to M locations with the objective of minimizing the total machine-to-machine material transportation cost in a flow line may be formulated as a quadratic assignment problem (QAP). Instead of having M unique machines, if an application involves one or more sets of identical machines, the location problem becomes a tertiary assignment problem (TAP). Solving a large problem of this kind is extremely difficult because of its combinatorial nature. When machine-to-machine flow is fixed, the TAP may be specialized to a QAP for which the unique machine problem is a special case. Obtaining an optimum solution to this problem when M is large is also computationally intractable. However, this problem may be solved by identifying sets of identical machines which may be partitioned into individual, "unique" machines. Properties of a special type of matrix called the amoebic matrix are used in the partitioned problems to provide approximate solutions, which are relabeled to prescribe a solution to the original problem. Results are demonstrated along with suggestions for further research.
- Published
- 1998
47. A tabu search algorithm for frequency assignment
- Author
-
D. J. Castelino, Stephen Hurley, and N. M. Stephens
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Quadratic assignment problem ,Frequency assignment ,General Decision Sciences ,Guided Local Search ,Management Science and Operations Research ,Algorithm ,Assignment problem ,Tabu search ,Weapon target assignment problem ,Generalized assignment problem ,Mathematics - Abstract
This paper presents the application of a tabu search algorithm for solving the frequency assignment problem. This problem, known to be NP-hard, is to find an assignment of frequencies for a number of communication links, which satisfy various constraints. We report on our computational experiments in terms of computational efficiency and quality of the solutions obtained for realistic, computer-generated problem instances. The method is efficient, robust and stable and gives solutions which compare more favourably than ones obtained using a genetic algorithm.
- Published
- 1996
48. A two-phase algorithm for the partial accessibility constrained vehicle routing problem
- Author
-
Frédéric Semet
- Subjects
Mathematical optimization ,Optimization problem ,Quadratic assignment problem ,General Decision Sciences ,Management Science and Operations Research ,symbols.namesake ,Lagrangian relaxation ,Vehicle routing problem ,symbols ,Combinatorial optimization ,Destination-Sequenced Distance Vector routing ,Algorithm ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
In the partial accessibility constrained vehicle routing problem, a route can be covered by two types of vehicles, i.e. truck or truck + trailer. Some customers are accessible by both vehicle types, whereas others solely by trucks. After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assignment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems.
- Published
- 1995
49. Lower bounds for the quadratic assignment problem
- Author
-
Yong Li, Panos M. Pardalos, K. G. Ramakrishnan, and Mauricio G. C. Resende
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Branch and bound ,Quadratic assignment problem ,General Decision Sciences ,Quadratic programming ,Management Science and Operations Research ,Upper and lower bounds ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.
- Published
- 1994
50. A robust heuristic for the Generalized Assignment Problem
- Author
-
Michael Racer and Mohammad M. Amini
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Duality gap ,Quadratic assignment problem ,General Decision Sciences ,Management Science and Operations Research ,Heuristics ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Consistent heuristic ,Mathematics - Abstract
The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few. Previous research has been concentrated on optimization methodologies for the GAP. Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic,Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. On difficult problem instances, VDSH provides solutions having costs 140% less than those found by the leading heuristic. A duality gap analysis of VDSH demonstrates the robustness of our heuristics.
- Published
- 1994
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.