Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 53 for “"Quadratic assignment problem"”.
-
Metaheuristics for the Generalized Quadratic Assignment Problem
The generalized quadratic assignment problem (GQAP) is the task of assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may have different space requirements, and the locations may have varying space …
-
Deterministic interchange algorithms for the quadratic assignment problem
The quadratic assignment problem (QAP) is a combinatorial optimization problem in which the total cost of an assignment of objects (facilities) to sites (locations) is to be minimized. Unlike the linear assignment problem, the QAP explicitly considers the costs associated with the flow or …
-
Simulated Annealing Heuristics for the Dynamic Generalized Quadratic Assignment Problem
The Dynamic Generalized Quadratic Assignment Problem (DGQAP) is the task of assigning a set of facilities to a set of locations in a multi-period planning horizon such that the sum of the transportation and assignment/reassignment costs is minimized. The facilities may have different space …
-
A flexible construction and improvement heuristic for the quadratic assignment problem
… of heuristic algorithms for the popular Quadratic Assignment Problem (QAP) which finds a wide variety of applications in various fields. This discrete optimization problem, which seeks the placement of m facilities on m locations in order to minimize a quadratic interactive cost, is well …
-
An exact branch and bound algorithm for the general quadratic assignment problem
… development of an exact algorithm for a general quadratic assignment problem (QAP), of which the Koopmans-Beckmann formulation, in the context of an analysis of the location of economic activities or facilities, is a special case. The algorithm is based on the linearization of a general QAP of …
-
Linear Programming Methods for Identifying Solvable Cases of the Quadratic Assignment Problem
… solvable instances of the celebrated NP-hard quadratic assignment problem (qap). The approach is novel in that it uses polyhedral methods based on an equivalent mixed 0-1 linear reformulation of the problem. The continuous relaxation of this mixed 0-1 form yields a feasible region having …
-
AN INVESTIGATION OF METAHEURISTICS USING PATH- RELINKING ON THE QUADRATIC ASSIGNMENT PROBLEM
The Quadratic Assignment Problem (QAP) is a widely researched, yet complex, combinatorial optimization problem that is applicable in modeling many real-world problems. Specifically, many optimization problems are formulated as QAPs. To resolve QAPs, the recent trends have been to use metaheuristics …
-
On the Computation of a Tight Lower Bound for the Quadratic Assignment Problem
… strategies for a specially-structured zero-one quadratic programming problem referred to as the Quadratic Assignment Problem (QAP).
-
ADMM for SDP Relaxation of GP
We consider the problem of partitioning the set of nodes of a graph G into k sets of given sizes in order to minimize the cut obtained after removing the k-th set. This is a variant of the well-known vertex separator problem that has applications in e.g., numerical linear algebra. This problem is …
-
A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM
… solution techniques of two NP-hard, large scale problems, the quadratic assignment problem, QAP, and the side chain positioning, SCP, problem. We summarize existing approaches from and look at the two problems in a unified way using a binary-constrained quadratic program, BCQP. We show how to …
-
A quadratic partial assignment and packing model and algorithm for the airline gate assignment problem
This thesis is concerned with an Airline Gate Assignment problem that seeks to allocate gates to aircraft at an airport, using the objective of minimizing passenger walking distances. The problem is modeled as a variant of the quadratic assignment problem with set packing constraints. The quadratic …
-
A Study and Design of an Automated Resource Allocation System
… ticket to its automatic tire-curing presses. The problem is of interest for the reason that the value of the objective function is markedly affected by the relative locations of tires amongst themselves. This consideration has negated the possibility of a solution being effected by the application …
-
An industrial application of a generalized quadratic assignment model for facility layout
… this investigation is to determine the optimal assignment of a given set of departments to a given set of locations so that all necessary floor space constraints are satisfied and the total number of distance-loads for all departments is minimized. An exact model formulation is given and a …
-
Experimenty s rojovou inteligencí (swarm intelligence)
… inteligence. Stručně popisuje biologické pozadí problematiky a zabývá se také principy hledání cest v mravenčích koloniích. Představena je i oblast kombinatorické optimalizace a detailně jsou definovány úlohy Travelling Salesman Problem a Quadratic Assignment Problem. Hlavní část práce sestává z …
-
Αλγόριθμοι τεχνητής ευφυΐας σμήνους και εφαρμογές σε μη-ντετερμινιστικά πολυωνυμικά προβλήματα
This thesis examines non deterministic polynomial problems in relation to the solutions proposed by Swarm Intelligence Algorithms. Many real life problems can be reduced to problems in the NP class and that is the reason they attract scientific interest. In this thesis, the problems that are …
-
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some …
-
ROCS: Robust Circular Seriation by Perturbation Entropy Minimization
… bound. Connections with the traveling salesman problem and the quadratic assignment problem are discussed and explored. Extensive empirical studies demonstrate the performance of the proposed approach in a variety of applications and the robustness of the algorithm against complex topologies and …
-
A water flow algorithm for optimization problems
… flow algorithm (WFA), for solving optimization problems has been proposed. The algorithm is designed by simulating the hydrological cycle in meteorology and the erosion phenomenon in nature. Basic operators of this algorithm are based on the raindrop distribution simulation, the property of …
Page 1 of 3