quadratic assignment problem np complete

Analysis of Algorithms
Backtracking
Dynamic Programming
Divide and Conquer
Geometric Algorithms
Mathematical Algorithms
Pattern Searching
Bitwise Algorithms
Branch & Bound
Randomized Algorithms

Quadratic Assignment Problem (QAP)

The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them.

The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.

The distance matrix and flow matrix, as well as restrictions to ensure each facility is assigned to exactly one location and each location is assigned to exactly one facility, can be used to formulate the QAP as a quadratic objective function.

The QAP is a well-known example of an NP-hard problem , which means that for larger cases, computing the best solution might be difficult. As a result, many algorithms and heuristics have been created to quickly identify approximations of answers.

There are various types of algorithms for different problem structures, such as:

Precise algorithms
Approximation algorithms
Metaheuristics like genetic algorithms and simulated annealing
Specialized algorithms

Example: Given four facilities (F1, F2, F3, F4) and four locations (L1, L2, L3, L4). We have a cost matrix that represents the pairwise distances or costs between facilities. Additionally, we have a flow matrix that represents the interaction or flow between locations. Find the assignment that minimizes the total cost based on the interactions between facilities and locations. Each facility must be assigned to exactly one location, and each location can only accommodate one facility.

Facilities cost matrix:

Flow matrix:

To solve the QAP, various optimization techniques can be used, such as mathematical programming, heuristics, or metaheuristics. These techniques aim to explore the search space and find the optimal or near-optimal solution.

The solution to the QAP will provide an assignment of facilities to locations that minimizes the overall cost.

The solution generates all possible permutations of the assignment and calculates the total cost for each assignment. The optimal assignment is the one that results in the minimum total cost.

To calculate the total cost, we look at each pair of facilities in (i, j) and their respective locations (location1, location2). We then multiply the cost of assigning facility1 to facility2 (facilities[facility1][facility2]) with the flow from location1 to location2 (locations[location1][location2]). This process is done for all pairs of facilities in the assignment, and the costs are summed up.

Overall, the output tells us that assigning facilities to locations as F1->L1, F3->L2, F2->L3, and F4->L4 results in the minimum total cost of 44. This means that Facility 1 is assigned to Location 1, Facility 3 is assigned to Location 2, Facility 2 is assigned to Location 3, and Facility 4 is assigned to Location 4, yielding the lowest cost based on the given cost and flow matrices.This example demonstrates the process of finding the optimal assignment by considering the costs and flows associated with each facility and location. The objective is to find the assignment that minimizes the total cost, taking into account the interactions between facilities and locations.

Applications of the QAP include facility location, logistics, scheduling, and network architecture, all of which require effective resource allocation and arrangement.

What kind of Experience do you want to share?

Quadratic Assignment Problem (QAP)

Andrey Karenskih

Jul 2, 2024

Introduction

The Quadratic Assignment Problem (QAP) is one of the fundamental optimization problems in operations research and has long been challenging to solve, particularly for dynamic, fast-changing scenarios. In this blog post, we demonstrate how we formulated the QAP as a QUBO problem, ran it on the LightSolver platform and benchmarked it against two solvers from the Google OR-Tools suite.

The Challenge: Real-time Assignments

Imagine you are the logistics manager of a bustling e-commerce warehouse, where hundreds of orders flood in every hour and new shipments of goods arrive continuously. Your challenge is to ensure that each item is stored in an optimal location to minimize the time and effort needed for picking and packing. As customer demands fluctuate and new products are introduced, the complexity of assigning storage locations dynamically increases. This is where the QAP comes into play, helping you determine the best arrangement of products to enhance efficiency, reduce operational costs, and accelerate order fulfillment in real-time.

Considered one of the most challenging NP-hard problems , the QAP has been used in fields like facility layout design, electronic design, and logistics, traditionally. It involves assigning a set of facilities to a set of locations in such a way that the total cost, influenced by both the distance between locations and the interaction between facilities, is minimized. Imagine trying to determine the best positions for machines in a factory or servers in a data center, where the objective is to reduce the total cost of transporting materials or data between them. The QAP captures this real-world problem, seeking an optimal solution among the many possible layouts. Despite its practical importance, solving QAP efficiently is notoriously difficult due to the combinatorial explosion of possible assignments as the number of facilities and locations increases.

This challenge becomes intractable with conventional computing platforms for dynamic use cases such as the above-mentioned e-commerce warehouse optimization, where solutions must be obtained within seconds or minutes to deliver optimal value. Additional dynamic QAP applications include network design in telecommunications (real-time allocation of transmitters to frequencies to adapt to traffic patterns), dynamic hospital layout (assigning rooms and facilities in function of needs and emergencies), path planning and task assignment for robot arms in manufacturing settings, dynamic electronic component placement for PCB assembly, emergency response resource allocation, and traffic flow management in smart cities. Delivering optimized solutions for such fast-paced scenarios demands advanced solving algorithms and highly efficient computing platforms.

Putting QUBO to work

quadratic assignment problem np complete

Let’s start by putting down the mathematical definition of the QAP: MATHEMATICAL DEFINITION

𝑛 facilities to be assigned to 𝑛 locations.
d i , j is the distance between location i and location j.
f i , j is the flow between facility i and facility j
A solution is a bijective function σ:{1,…,n}→{1,…,n} which assigns facility i to location σ(i)
For a given solution σ, the objective value of QAP is: ∑ i , j f i , j d σ i , σ j

Our goal is to find an assignment σ that minimizes the cost defined above. QUBO FORMULATION Here is how we created the QUBO:

We introduce the binary variables x ij that represent the assignment of the ith facility to the j th location.
For σ to be bijective we must have each facility assigned to exactly one factory. To achieve this, we add a penalty term if these conditions are violated: P e n a l t y x = λ ∑ i ∑ j x i j – 1 2 + λ ∑ j ∑ i x i j – 1 2
The objective value introduced before can be expressed in terms of the variables x i j as follows: Obj ( x ) = ∑ i , j , k , l f ij d kl x ik x jl
Finally, the QUBO formulation for a QAP problem is: m i n χ i , j ∈ { 0 , 1 } O b j x + Penalty x

Benchmark against Google OR-Tools Solvers

To evaluate the feasibility of our platform for dynamic QAP use cases, we decided to limit the run time for this benchmark to 60 seconds. We chose data sets from the COR@L library , starting with instances of 12 locations and increasing the problem size until the solvers were unable to provide solutions. Our evaluation criterium was the solution quality, expressed by the size of the gap from the best-known objective value, with the smallest gap being the best result. Here is how the LightSolver platform performed against CP-SAT and GSCIP from the Google-OR package 9.9.3963:

LightSolver constantly delivered higher solution quality (smaller gaps from the optimal known solution) than the two Google OR-Tools solvers, regardless of the problem size. Within the set runtime, CP-SAT could not generate solutions for instances with 50+ facilities, nor could GSCIP for problems of 60+ facilities.

Since its initial introduction in the 1950s, the QAP continues to challenge the operations research community. Despite the amount of data available in real time today, many solvers cannot generate solutions for dynamic scenarios due to the explosion of combinatorial possibilities. LightSolver’s platform delivers accurate and ultra-fast solutions that enable organizations to optimize their operations, saving valuable time, resources, and in the case of emergency response resource allocation, even lives.

Would you like to see how LightSolver can tackle YOUR optimization challenge? Contact us at [email protected]

About the author

Andrey Karenskih is a simulation and benchmark expert at LightSolver and has a background in algorithm research and machine learning. When not working at the office or studying for his M.Sc. in mathematics at Tel Aviv University, Andrey enjoys doing origami. His most complex project so far is a crocodile comprised of over 300 steps, created over three days with very short nights.

BOOK A DEMO

Lightsolver – website terms of use.

LightSolver Ltd., its parent company and its affiliates (“ LightSolver ”, “we”, “our” or “ us ”) welcome you to our website at https://lightsolver.com/ (the “ Site ”).Our Site offers basic information on our company and technology. These Website Terms of Use (these “ Terms ”) govern your access to and use of the Site.

All references to “ you ”or “ User ,” as applicable, mean the person who enters, connects to, accesses, or uses the Site in any manner, and each of your heirs, assigns, and successors. If you use the Site on behalf of an entity, you represent and warrant that you have the authority to bind that entity, your acceptance of these Terms will be deemed an acceptance by that entity, and “you” and “your”herein shall refer to that entity, its directors, officers, employees, and agents.

1. Acceptance of These Terms

BY ENTERING, CONNECTING TO,ACCESSING AND/OR USING THE SITE, YOU ACKNOWLEDGE THAT YOU HAVE READ AND UNDERSTOOD THESE TERMS, AND YOU AGREE TO BE BOUND BY THEM AND TO COMPLY WITH ALL APPLICABLE LAWS AND REGULATIONS REGARDING YOUR USE OF THE SITE. YOU ACKNOWLEDGE THAT THESE TERMS CONSTITUTE A BINDING AND ENFORCEABLE LEGAL CONTRACT BETWEEN LIGHSOLVER AND YOU. . IF YOU DO NOT AGREE TO THESE TERMS, PLEASE DO NOT ENTER, CONNECT, ACCESS OR USETHE SITE IN ANY MANNER.

2. The Site

The Site includes informative pages on our product(s) and service(s), as well as our company. In addition, there are forms that Users may fill in, which include, without limitation: (i)“Contact Us” form; (ii) “Demo Request Form”; (iii) “About Us” – enabling Users to learn more about us; (v) “Solutions”– enabling Users to learn about LightSolver’s technology, products and services; and (vi) “Careers” – enabling potential candidates to apply for job opportunities at LightSolver. To learn more about the information you provide us when filling in one or more of the forms, please review our to apply for job opportunities at LightSolver. To learn more about the information you provide us when filling in one or more of the forms, please review our Website PrivacyPolicy at(“ PrivacyPolicy ”).

3. Use Restrictions

There is certain conduct which is strictly prohibited on the Site. Please read the following restrictions carefully. Your failure to comply with the provisions set forth below may, at LightSolver’s sole discretion, result in the termination of your access to the Site and may also expose you to civil and/ or criminal liability.

You will not, and you will not direct any third parties to: (i) copy, scrape, modify, create derivative works of, adapt, emulate, translate, reverse engineer, compile, decompile or disassemble any portion of the content on theSite and any other information, documents, material and data available on theSite (collectively, the “ Content ”)in any way, or publicly display, perform, or distribute the Content, without LightSolver’s prior written consent; (ii) make any use of the Content on any other website or networked computer environment for any purpose, or replicate or copy theContent without LightSolver’s prior written consent; (iii) create a browser or border environment around theSite and/or Content, link, including in-line linking, to elements on the Site, such as images, posters and videos, and/or frame or mirror any part of theSite; (iv) transmit, distribute, display or otherwise make available through orin connection with the Site any content which may infringe third party rights, including intellectual property rights and privacy rights, or which may contain any unlawful content; (v) transmit or otherwise make available in connection with the Site, and/or use the Site to distribute and/or otherwise transmit any virus, worm, trojan horse, time bomb, web bug, spyware, or any other computer code, file, or program that mayor is intended to damage or hijack the operation of any hardware, software, or telecommunications equipment, or any other actually or potentially harmful, disruptive, or invasive code or component; (vi) interfere with or disrupt the operation of the Site, or the servers or networks that host the Site or make the Site available, or disobey any requirements, procedures, policies, or regulations of such servers or networks; or (vii) use the Content and/or theSite for any illegal, immoral or unauthorized purpose.

4. Privacy Policy

We respect the privacy of ourUsers and are committed to protecting the information you share with us in connection with your use of the Site. Our policy and practices and the type of information collected are described in our PrivacyPolicy[H.A.1] , which is incorporated herein by reference. By connecting to, accessing or using the Site, you acknowledge that you have read and agree to the Privacy Policy .

5. License

LightSolver grants you a limited, personal, non-exclusive, non-assignable, not-tradeable, non-sub-licensable, fully and immediately revocable at LightSolver’s discretion, license, to use the Site and reproduce and display any Content made available for download and downloaded by you from the Site (the “ Materials ”), solely for your personal and non-commercial use, all subject to the terms and conditions in these Terms. These Terms do not entitle you with any right in the Site or in the Content or Materials, rather only to a limited right to use the same it in accordance herewith.

The Materials are made available to you subject to the terms of Section 3 above, for your own personal limited use, and without derogating from the restrictions set forth under theseTerms and in addition thereto, you may not: (i) distribute the Materials or any part thereof, directly or indirectly; (ii) make or allow any third party to make any commercial use of the Materials; and (iii) modify, add, subtract, aggregate or otherwise make any derivative work of the Materials or allow a third party to do so.You hereby agree that uponCompany’s request you will immediately return all Materials, purge your systems from any Materials and ensure that no copies, extracts or other reproductions are retained by you.

6. Feedback

In the event that you provide LightSolver with any suggestions, comments or other feedback relating to Site and/or LightSolver products and/or services (collectively, “ Feedback ”),such Feedback is deemed as the sole and exclusive property of LightSolver and you hereby irrevocably assign to LightSolver all of its rights, title and interest in and to all Feedback, if any, and waive any moral rights to it (or anyone on your behalf) may have in such Feedback. By sending us any Feedback, you hereby represent and warrant that (a) you have the right to disclose the Feedback, (b)the Feedback does not violate the rights of any other individual or entity, and(c) your Feedback does not contain the confidential or proprietary information of any third party. By sending us any Feedback, you further (i) agree that we are under no obligation of confidentiality, express or implied, with respect to the Feedback and (ii) acknowledge that we may have something similar to theFeedback already under consideration or in development. You shall promptly inform LightSolver as soon as you become aware of any third party right or imitation which may apply to Feedback already provided. This Section 6 shall survive any termination of your access to the Site or any of our products or services.

7. Intellectual Property Rights

“ LightSolver Intellectual Property ” means any and all proprietary and intellectual property rights, including the Site, its logos, graphics, icons, images, as well as the selection, assembly and arrangement thereof, LightSolver’s proprietary software, algorithms and any and all intellectual property rights pertaining thereto, including, without limitation, inventions, patents and patent applications, trademarks, trade names, logos, copyrightable materials, graphics, text, images, designs (including the “look and feel” of the Site and any part thereof), specifications, methods, procedures, information, know-how, data, technical data, interactive features, source and object code, files, interface and trade secrets, whether or not registered and/or capable of being registered, and any and all Feedback.

The LightSolver Intellectual Property is owned by and/or licensed to LightSolver and is subject to copyright and other applicable intellectual property rights under local laws, foreign laws and international conventions. You may not copy, distribute, display, execute publicly, make available to the public, emulate, reduce to human readable form, decompile, disassemble, adapt, sublicense, make any commercial use, sell, rent, lend, process, compile, reverse engineer, combine with other software, translate, modify or create derivative works of any material that is subject to LightSolver’s proprietary rights, including the LightSolver Intellectual Property, either by yourself or by anyone on your behalf, in any way or by any means, unless expressly permitted in these Terms.

“LightSolver” and all logos and other proprietary identifiers used by LightSolver in connection with the Site (“ LightSolver Trademarks ”), are all trademarks and/or trade names of LightSolver, whether or not registered. All other trademarks, Site marks, trade names and logos which may appear on or with respect to the Site belong to their respective owners (“ Third Party Marks ”).No right, license, or interest to LightSolver Trademarks and/or to the Third Party Marks is granted hereunder, and you agree that no such right, license, or interest shall be asserted by you with respect to LightSolver Trademarks or the Third Party Marks and therefore you will avoid using any of those marks, unless expressly permitted herein. You are hereby prohibited from removing or deleting any and all copyright notices, restrictions and signs indicating proprietary rights of LightSolver and/or its licensors, including copyright mark © or trademark ® or ™ contained in or accompanying the Site, and you represent and warrant that you will abide by all applicable laws in this respect. You are further prohibited from using, diluting or staining any name, mark or logo that is identical, or confusingly similar to any of LightSolver’s marks and logos, whether registered or not.

No licenses or rights are granted to you by implication or otherwise under any LightSolver Intellectual Property, except for the licenses and rights expressly granted in these Terms.

8. Third Party Components

The Site may use or include third party software, files and components that are subject to open source and third party license terms (“ Third PartyComponents ”). Your right to use such Third Party Components as part of, orin connection with, the Site is subject to any applicable acknowledgements and license terms accompanying such Third Party Components, contained therein or related thereto. These Terms do not apply to any Third Party Components accompanying or contained in the Site, and LightSolver disclaims all liability related thereto. You acknowledge that LightSolver is not the author, owner or licensor of any Third Party Components, and that LightSolver makes no warranties or representations, express or implied, as to the quality, capabilities, operations, performance or suitability of Third Party Components.Under no circumstances shall the Site or any portion thereof (except for theThird Party Components contained therein) be deemed to be “open source” or“publicly available” software.

9. Availability

The Site’s availability and functionality depend on various factors, such as communication networks, software, hardware, and LightSolver’sSite providers and contractors. LightSolver does not warrant or guarantee that the Site will operate and/ or be available at all times without disruption or interruption, or that it will be immune from unauthorized access or error-free.

10. Changes to the Site

LightSolver reserves the right, at its sole discretion, to modify, correct, amend, enhance, improve, make any other changes to, or discontinue, temporarily or permanently, the Site(or any part thereof) without notice, at any time. In addition, you hereby acknowledge that the Content available through the Site may be changed, modified, edited or extended in terms of content and form or removed at anytime without any notice to you. You agree that LightSolver shall not be liable to you or to any third party for any modification, suspension, error, malfunction or discontinuance of the Site (or any part thereof).

11. Disclaimer and Warranties

LIGHTSOLVER DOES NOT WARRANT ORMAKE ANY REPRESENTATIONS REGARDING THE USE, THE INABILITY TO USE OR OPERATE, ORTHE RESULTS OF THE USE OR OPERATION OF THE SITE (OR ANY PART THEREOF). LIGHTSOLVER SHALL NOT BE LIABLE FOR ANY DAMAGES WHATSOEVER, INCLUDING, BUT NOT LIMITED TO,DIRECT, INDIRECT, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND,WHETHER IT WAS CAUSED CONSEQUENTLY OR IN CONNECTION WITH THE USE OF THE SITE,WHETHER OR NOT LIGHTSOLVER HAD INFORMED THE USER OF SUCH POSSIBLE DAMAGE.

THE SITE (AND ANY PART THEREOF), INCLUDING WITHOUT LIMITATION ANY CONTENT, DATA AND INFORMATION RELATED THERETO, ARE PROVIDED ON AN “AS IS” AND “AS AVAILABLE” BASIS, WITHOUT ANY WARRANTIES OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING WARRANTIES OF TITLE OR NON-INFRINGEMENT OR IMPLIED WARRANTIES OF USE, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE OR USE. LIGHTSOLVER DISCLAIMS AND MAKES NORE PRESENTATIONS OR WARRANTIES AS TO THE ACCURACY, QUALITY, AVAILABILITY,RELIABILITY, SUITABILITY, COMPLETENESS, TRUTHFULNESS, USEFULNESS, OR EFFECTIVENESS OF ANY CONTENT AVAILABLE ON OUR SERVICES. LIGHTSOLVER AND ANY OF ITS OFFICERS, DIRECTORS, SHAREHOLDERS, EMPLOYEES, SUB-CONTRACTORS, SERVICE PROVIDERS, AGENTS AND OTHER AFFILIATED ENTITIES (COLLECTIVELY, “LIGHTSOLVER PARTIES”),JOINTLY AND SEVERALLY, DISCLAIM AND MAKE NO REPRESENTATIONS OR WARRANTIES AS TOTHE USABILITY, ACCURACY, QUALITY, AVAILABILITY, RELIABILITY, SUITABILITY,COMPLETENESS, TRUTHFULNESS, USEFULNESS, OR EFFECTIVENESS OF ANY CONTENT, DATA,RESULTS, OR OTHER INFORMATION OBTAINED OR GENERATED IN CONNECTION WITH YOUR ORANY USER’S USE OF THE SITE. LIGHTSOLVER DOES NOT WARRANT THAT THE OPERATION OFTHE SITE IS OR WILL BE SECURE, ACCURATE, COMPLETE, UNINTERRUPTED, WITHOUT ERROR, OR FREE OF VIRUSES, WORMS, OTHER HARMFUL COMPONENTS, OR OTHER PROGRAM LIMITATIONS. LIGHTSOLVER MAY, AT ITS SOLE DISCRETION AND WITHOUT AN OBLIGATION TO DO SO, CORRECT, MODIFY, AMEND, ENHANCE, IMPROVE AND MAKE ANY OTHER CHANGES TO THE SITE AT ANY TIME, OR DISCONTINUE DISPLAYING OR PROVIDING ANY CONTENT OR FEATURES WITHOUT ANY NOTICE TO YOU. YOU AGREE AND ACKNOWLEDGE THAT THE USE OFTHE SITE, INCLUDING USE OF AND/OR RELIANCE ON ANY CONTENT AVAILABLE THROUGH THE SITE, IS ENTIRELY, OR OTHERWISE TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, AT YOUR OWN RISK.

12. Limitation of Liability

YOU ACKNOWLEDGE AND AGREE THAT, TO THE MAXIMUM EXTENT PERMITTED BY LAW, THE ENTIRE RISK ARISING OUT OFYOUR ACCESS TO AND USE OF THE SITE REMAINS WITH YOU. IN NO EVENT SHALL LIGHTSOLVER AND/OR ANY OF THE LIGHTSOLVER PARTIES BE LIABLE FORANY DAMAGES WHATSOEVER, INCLUDING DIRECT, INDIRECT, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, RESULTING FROM OR ARISING OUT OF THE SITE,USE OR INABILITY TO USE THE SITE, FAILURE OF THE SITE TO PERFORM AS REPRESENTED OR EXPECTED, LOSS OF GOODWILL, DATA OR PROFITS, THE PERFORMANCE OR FAILURE OF LIGHTSOLVER TO PERFORM UNDER THESE TERMS, AND ANY OTHER ACT OR OMISSION OF LIGHTSOLVER BY ANY OTHER CAUSE WHATSOEVER, INCLUDING WITHOUT LIMITATION DAMAGES ARISING FROM THE CONDUCT OF ANY USERS AND/OR THIRD PARTY SITES.

NO ACTION MAY BE BROUGHT BY YOUFOR ANY BREACH OF THESE TERMS MORE THAN ONE (1) YEAR AFTER THE ACCRUAL OF SUCH CAUSE OF ACTION. AS SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF INCIDENTAL OR CONSEQUENTIAL DAMAGES, THEN SUCH LIMITATIONS ONLY MAY NOT APPLY TO A USER RESIDING IN SUCH STATES.

SUCH LIMITATIONS, EXCLUSIONS AND DISCLAIMERS SHALL APPLY TO ALL CLAIMS FOR DAMAGES, WHETHER BASED IN AN ACTION OF CONTRACT, WARRANTY, STRICT LIABILITY, NEGLIGENCE, TORT, OR OTHERWISE.YOU HEREBY ACKNOWLEDGE AND AGREE THAT THESE LIMITATIONS OF LIABILITY ARE AGREED ALLOCATIONS OF RISK CONSTITUTING IN PART THE CONSIDERATION FOR LIGHTSOLVER’S SITE TO YOU, AND SUCH LIMITATIONS WILL APPLY NOTWITHSTANDING THE FAILURE OF ESSENTIAL PURPOSE OF ANY LIMITED REMEDY, AND EVEN IF LIGHTSOLVER AND/ORANY LIGHTSOLVER PARTIES HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH LIABILITIES AND/OR DAMAGES. THE FOREGOING LIMITATION OF LIABILITY SHALL APPLY TO THE FULLEST EXTENT PERMITTED BY LAW IN THE APPLICABLE JURISDICTION AND IN NO EVENT SHALL LIGHTSOLVER’S CUMULATIVE LIABILITY TO YOU EXCEED $100.

13. Indemnification

You agree to defend, indemnify and hold harmless LightSolver and any LightSolver Parties from and against any and all claims, damages, obligations, losses, liabilities, costs, debts, fines, late fees, cancellation fees and expenses (including attorney’s fees) arising directly or indirectly from: (i) your use of the Site (or any part thereof); (ii) breach of any term of these Terms by you or anyone on your behalf; (iii) any damage of any sort, whether direct, indirect, special or consequential, you may cause to any third party which relates to your use of (or inability to use) the Site; (iv) your violation of the Privacy Policy, any third party intellectual property rights, privacy rights or other rights through your use of the Site or provision of information; and (v) your violation of any applicable law or regulation.

Notwithstanding the foregoing paragraph, if you are a resident of New Jersey, you only agree to release, defend, indemnify, and hold LightSolver, and its officers, directors, employees and agents, harmless from and against any third-party claims, liabilities, damages, losses, and expenses, including reasonable legal and accounting fees, arising out of or in any way connected with your violation of these Terms.

14. Amendments to the Terms

LightSolver reserves the right to change these Terms, and any other documents incorporated by reference herein, from time to time, at its sole discretion and without any prior notice.LightSolver will notify you regarding material changes of the terms of theseTerms by notice on the Site or by sending you an e-mail regarding such changes to the e-mail address that you provided in the registration form. Such material changes will take effect seven (7) days after such notice is provided on ourSite or sent by email. Otherwise, changes to these Terms are effective upon notice being given, which may be made by posting the changes to these Terms on the Site. You are responsible for regularly reviewing these Terms for updates and modifications. Your continued use of the Site after notice of changes has been given will constitute acceptance of, and agreement to be bound by, those changes. If you do not agree, you may not access or use the Site.

To use the Site, you must be over the age of seventeen (17). We reserve the right to request proof of age at any stage so that we can verify that persons under the age of seventeen (17)are not using the Site. In the event that it comes to our knowledge that a person under the age of seventeen (17) is using the Site, we will prohibit and block such User from accessing the Site and will make all efforts to promptly delete any Personal Information (as such term is defined in our Privacy Policy with regard to such User.

16. General

These Terms do not, and shall not be construed to create any partnership, joint venture, employer-employee, agency, or franchisor-franchisee relationship between the parties hereto. Any claim relating to this Site or use of this Site will be governed by and interpreted in accordance with the laws of the State of California, UnitedStates, without reference to its conflict-of-laws principles. Any dispute arising out of or related to your use of this Site will be brought in, and you hereby consent to exclusive jurisdiction and venue in, the competent courts of the applicable court in the state of California, United States. If any provision of these Terms is found to be unlawful, void, or for any reason unenforceable, then that provision will be deemed severable from these Terms and will not affect the validity and enforceability of any remaining provision.You may not assign, sublicense or otherwise transfer any or all of your rights or obligations under these Terms without LightSolver’s prior express written consent. No waiver by either party of any breach or default hereunder will be deemed to be a waiver of any preceding or subsequent breach or default. Any heading, caption or section title contained herein is inserted only as a matter of convenience, and in noway defines or explains any section or provision hereof. These Terms are the entire terms and conditions between you and LightSolver relating to the subject matter herein and supersedes any prior or contemporaneous written or oral agreements or understandings between you and LightSolver. Notices to you may be made via email or regular mail. This Site may also provide notices of changes to theseTerms or other matters, by displaying such notices or by providing links to such notices. Without limitation, you agree that a printed version of theseTerms and of any notice given in electronic form shall be admissible in judicial or administrative proceedings based upon or relating to these Terms to the same extent and subject to the same conditions as other business documents and records originally generated and maintained in printed form.

17. Interpretation

For purposes of these Terms:

(i) the words “include,”“includes” and “including” shall be deemed to be followed by the words “without limitation”;

(ii) the word “or” is not exclusive;

(iii) the word “any” means “any and all”;

(iv) the words “herein,” “hereof,” “hereby,” “hereto” and “hereunder” refer to these Terms as a whole;

(v) the headings in these Terms are for reference only and shall not affect the interpretation of these Terms;

(vi) when a reference is made to a Section, such reference shall be to a Section of these Terms; and

(vii) unless the context requires otherwise, words using the singular or plural number also include the plural or singular number, respectively, and references to a “person” includes both individuals and entities and their permitted successors and assigns.

This Terms were written inEnglish and may be translated into other languages for your convenience. If a translated (non-English) version of these Terms conflicts in any way with theEnglish version, the provisions of the English version shall prevail.

18. Contact Us

If you have any questions or comments concerning these Terms or the Site, you are welcome to send us an email at the following address: [email protected] .

LightSolver – Website Privacy Policy

LightSolver Ltd., its parent company and its affiliates (“ LightSolver ”,“ we ”, “ our ” or “us”) respects the privacy of the users of its website at the address https://lightsolver.com/ (the“ Site ”) and is committed to the protection of the Personal Information (as defined below) that its Users share with it. We believe that you have a right to know our practices regarding the information we may collect and use when you visit or use our Site .

This Website Privacy Policy (this “ Privacy Policy ”) constitutes a binding and enforceable legal instrument between LightSolver and you – so please read it carefully. Capitalized terms that are used but not defined herein, as well as the terms “ you ” and “ User ,” shall have the meaning ascribed to them in our Website Terms of Use (“ Terms of Use ”), which incorporate the terms of this Privacy Policy by reference.

1. Your Consent

BY ENTERING, CONNECTING TO,ACCESSING AND/OR USING THE SITE, YOU AGREE TO THE TERMS AND CONDITIONS SET FORTH IN THIS PRIVACY POLICY, INCLUDING WITH RESPECT TO THE COLLECTION AND PROCESSING OF YOUR PERSONAL INFORMATION (AS DEFINED BELOW). IF YOU DISAGREE WITH ANY TERM PROVIDED HEREIN, YOU MAY NOT USE THE SITE.

2. Information We Collect

a. The first type of information is non-identifiable and anonymous information (“ Non-Personal Information ”). We are not aware of the identity of the User from which we have collected Non-Personal Information. Non-Personal Information is any unconcealed information which is available to us while Users are using the Site. Non-Personal Information which is being gathered consists of technical and behavioral information, and may contain, among other things, the activity of the User on the Site, a User’s “click-stream”on the Site, etc.

b. The second type of information is information which identifies an individual, or may with reasonable effort identify an individual, either alone or in combination with other information ( “Personal Information” ). This information may identify you or be otherwise associated with you. The PersonalInformation that we gather consists of any personal details provided voluntarily by the User or on their behalf. The Personal Information required from the User while filling in the contact forms (including the “Login” feature, the “Support” options or use of the Site’s chat widget) may include the User’s full name, e-mail address, phone number, country, company, job title and ICCID (IntegratedCircuit Card Identification Number) and the User may also voluntarily provide other information in free text fields as part of a dedicated message to us.

For the avoidance of doubt, any Non-Personal Information connected or linked to any Personal Information shall be deemed Personal Information for as long as such connection or linkage exists. Under this Privacy Policy, the term “information” shall mean both Personal and Non-Personal Information.

We do not collect any PersonalInformation from you without your approval, which is obtained, inter alia , through your acceptance of the Terms of Use and this Privacy Policy.

3. Methods of Information Collection

We collect information via the following methods:

a. We automatically collect information through your use of the Site. As you navigate through and interact with our Site, we may use automatic data collection technologies (like browser cookies and flash cookies) to gather, collect and record certain information about your equipment, browsing actions, and patterns, including details of your visits to our Site and information about your computer and internet connection (such as your IP address, operating system, and browser type), either independently or through the help of third-party services, as detailed below.

b. We collect information which you provide us voluntarily and with your consent . For example, we collect Personal Information which you voluntarily provide when you fill different forms on the Site or contact us in any other way. We store the Personal Information either independently or through the help of our authorized third-party service providers, as detailed below.

c. We use third party software and services to collect information . Third parties may collect and process information such as usage analytics data in order to provide and operate the Site and improve our products and services.

4. Purposes of Collection

a. We collect, process and use your information for the purposes described in this PrivacyPolicy, based at least on one of the following legal grounds:

i. With your consent: We ask for your consent, under this Privacy Policy, to process your information for specific purposes and you have the right to withdraw your consent at any time.

ii. When providing you with access to the Site: We collect and process your information in order to (i) provide you access to the Site; (ii) to maintain and improve our Site; (iii) to develop new services and features for our Users; (iv) and to personalize the Site in order for you to get a better user experience.

iii. Legitimate interests: We process your information for our legitimate interests while applying appropriate safeguards that protect your privacy. This means that we process your information for things like detecting, preventing, or otherwise addressing fraud, abuse, security, usability, functionality or technical issues with our services, protecting against harm to the rights, property or safety of our properties, or our users, or the public as required or permitted by law; enforcing legal claims, including investigation of potential violations of this PrivacyPolicy; in order to comply or fulfill our obligations under applicable laws, contractual requirements, legal process, subpoena or governmental request, as well as to enforce our Terms of Use.

b. Non-Personal Information and PersonalInformation are collected in order to:

i. to provide you with and to operate the Site, including for statistical and research purposes and creation of aggregated and/ or anonymous data;

ii. to develop, improve and customize the Site, the experience of other users and the offering available through the Site;

iii. to be able to contact you for the purpose of providing you with technical assistance, support, handle requests and complaints and collect feedback in connection with performance of the Site;

iv. to send you updates, notices, announcements, and additional information related to the Site

v. to be able to reply to your online queries in connection with performance of theSite;

vi. to display or send to you marketing and advertising material when you are using the Site, including in accordance with the section titled ‘Direct Marketing’ herein; and

vii. to comply with any governmental agencies’ legal requests or court orders, or with any applicable law, rule or regulation.

5. Sharing Information With Third Parties

LightSolver may disclose Personal Information in the following cases: (a) to comply with any applicable law, regulation, legal process, subpoena or governmental request; (b) to enforce the Terms of Use (including this Privacy Policy) or any other agreements between you (or any persons affiliated with you) and us, including investigation of potential violations thereof; (c) to detect, prevent, or otherwise address fraud, security or technical issues; (d) to respond to your support requests; (e) to respond to claims that any content available on the Site violates the rights of third parties; (f) to respond to claims that contact information (e.g., name, e-mail address) of a third party has been posted or transmitted without their consent or as a form of harassment; (g) to protect the rights, property, or personal safety of LightSolver, its Users, or any other person;(h) in connection with a change in control of LightSolver, including by means of merger, acquisition or sale of all or substantially all of its assets; (i) to LightSolver’s third-party service providers that provide services to LightSolver to facilitate our operation of the Site or our services (e.g., Amazon Web Services); (j) for any other purpose disclosed by us when you provide the Personal Information; or (k)pursuant to your explicit approval prior to such disclosure. For avoidance of doubt, LightSolver may transfer and disclose Non-Personal Information to third parties in its sole discretion.

Except as otherwise stated in this Privacy Policy, we do not sell, trade, share, or rent your Personal Information collected from our services to third parties. We may however transfer, share or otherwise use anonymized, aggregated or non-personal information in our sole discretion and without the need for further approval. You expressly consent to the sharing of your Personal Information as described in this Privacy Policy.

6. Modification or Deletion of Personal Information

We retain the Personal Information we collect only for as long as needed in order to provide you with our services and to comply with applicable laws and regulations. We then either delete from our systems or anonymize it without further notice to you. If for any reason you wish to request a modification to, or deletion of, your Personal Information in accordance with Section 13 of this Privacy Policy, you may do so by contacting LightSolver at [email protected] or through the Site.

However, please note that, although your Personal Information may be removed from our systems, LightSolver will retain any anonymous information contained therein or any anonymized or aggregate data derived therefrom, and such information will be owned by us and may continue to be used by us for any purpose, including the operation or improvement of our services.

To use the Site, you must be over the age of seventeen (17). Therefore, LightSolver does not knowingly collect Personal Information from persons under the age of seventeen (17) and does not wish to do so. We reserve the right to request proof of age at any stage so that we can verify that persons under the age of seventeen (17) are not using the Site.

8. Security

We take a great care in implementing and maintaining the security of LightSolver’s Site and its User’s PersonalInformation. LightSolver employs industry-standard procedures and policies to ensure the safety of its Users’ Personal Information and prevent unauthorized access to or use of any such information. However, we do not and cannot guarantee that unauthorized access or use will never occur.

9. Third Party Software/ Services

In order to provide and operate the Site, we use third-party software and services to collect and process the information detailed herein, and to improve our products and services. Examples include: web hosting, sending communications, analyzing data and conducting customer relationship management. These third-party service providers have access to the information needed to perform their respective functions, but may not use it for other purposes unless such data has been first anonymized. Further, they must process that information in accordance with this Privacy Policy and as permitted by applicable law.

10. Cookies & Local Storage

LightSolver may use industry-standard technologies, such as “cookies” or similar technologies, which store certain information about you on your computer and allow us to enable the automatic activation or personalization of certain features, there by making your interactions with us more convenient and efficient. The cookies that we use are created per session and do not include any information about you, other than your session key (which is generally removed at the end of your session). Most browsers will allow you to easily erase cookies from your computer’s hard drive, block acceptance of cookies, or receive a warning before a cookie is stored. However, if you block or erase cookies, your online experience and our ability to provide the Services to your Advisor may be limited or degraded. We do not respond to do-not-track signals.

11. Where Do We Store User’s Personal Information?

Information regarding theUsers will be maintained, processed and stored by us and our authorized affiliates and service providers in the United States and, as necessary, in secured cloud storage provided by our third-party service provider(s), which may include facilities located outside of the aforementioned location. You hereby accept the place of storage and the transfer of information as described above.

12. Job Candidates

LightSolver welcomes all qualified candidates(“ Candidates ”) to apply to any of the open positions posted on our Site or otherwise (including without limitation – Facebook and LinkedIn) by sending us their contact details and resumes(“ Candidate Information ”). We are committed to keep CandidateInformation private and use it solely for our internal recruitment purposes(including for identifying Candidates, evaluating their applications, making hiring and employment decisions, and contacting Candidates by phone or in writing).

Please note that we may retain Candidate Information submitted to us even after the applied position has been filled or closed. This is done so we may re-consider Candidates for other positions and opportunities at LightSolver; so we may use such CandidateInformation as reference for future applications; and in case the Candidate is hired, for additional employment and business purposes related to their employment or engagement with LightSolver.

If you previously submitted your Candidate Information to LightSolver and now wish to access it, update it or have it deleted from our systems, please contact us at: [email protected] .

13. Updating, Obtaining a Copy of, or Deleting Your Personal Information

If the law applicable to you grants you such rights, you may ask to access, correct, or delete your Personal Information that is stored in our systems. You may also ask for our confirmation as to whether or not we process your Personal Information.

Subject to the limitations in law, you may request that we update, correct, or delete inaccurate or outdated information. You may also request that we suspend the use of anyPersonal Information whose accuracy you contest while we verify the status of that information.

Subject the limitations in law, you may also be entitled to obtain the Personal Information you directly provided us (i.e., excluding data we obtained from other sources) in a structured, commonly used, and machine-readable format and may have the right to transmit such data to another party.

If you wish to exercise any of these rights, contact us at: [email protected] . When handling these requests, we may ask for additional information to confirm your identity and your request. Please note, upon request to delete yourPersonal Information, we may retain such data, in whole or in part, to comply with any applicable rule or regulation, and/or to respond to or defend against legal proceedings.

To find out whether these rights apply to you and on any other privacy related matter, you can contact your local data protection authority if you have concerns regarding your rights under local law.

14. Direct Marketing

You hereby agree that we may use your contact details provided during registration or otherwise volunteered through the Site for the purpose of informing you regarding our products and services, the Site and other news which may interest you, and to send to you other marketing material about related products and services offered by LightSolver. You may withdraw your consent by sending a written notice to LightSolver by email to the following address: [email protected] or by pressing the “Unsubscribe” button in the email.

15. Changes to This Privacy Policy

The terms of this PrivacyPolicy will govern your interaction with us and your use of the Site and any information collected in connection therewith. LightSolver may change thisPrivacy Policy from time to time, in our sole discretion and without any notice. LightSolver will notify you regarding material changes of the terms of this Privacy Policy by notice on the Site or by sending you an e-mail regarding such changes to the e-mail address that you provided in the registration form. Such material changes will take effect seven (7) days after such notice is provided on our Site or sent by email. Otherwise, Changes to this Privacy Policy are effective as of the stated “Last Updated” date and your continued use of the Site after the “Last Updated” date will constitute your acceptance of, and agreement to be bound by, such changes. You are responsible for periodically visiting our Site and this Privacy Policy to check for any changes. IF YOU DO NOT AGREE WITH CHANGES TO THE TERMS OF THIS PRIVACY POLICY, YOU ARE OBLIGATED TO PROMPTLY NOTIFY US AND TERMINATE YOUR USE OF THE SITE.

16. Contact Us

If you have any questions (or comments) concerning this Privacy Policy, you are welcome to send us an email at the following address: [email protected].

Your message was submitted successfully

A comprehensive review of quadratic assignment problem: variants, hybrids and applications

Original Research
Published: 20 June 2018

Cite this article

Mohamed Abdel-Basset ORCID: orcid.org/0000-0002-5572-0721 1 ,
Gunasekaran Manogaran 2 ,
Heba Rashad 1 &
Abdel Nasser H. Zaied 3

2758 Accesses

34 Citations

Explore all metrics

The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size increases, hence heuristic and metaheuristic approaches are utilized for solving the problem instead of exact approaches, because these approaches achieve quality in the solution in short computation time. The objectives of this paper are to describe QAP in details showing its types, nature of the problem, complexity of the problem, importance, and simple example. QAP formulations, problems related with QAP, solution techniques, QAP benchmark instances, applications of QAP, survey of QAP researches are also illustrated.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Quadratic Assignment Problems

Metaheuristics with Local Search Miscellany Applied to the Quadratic Assignment Problem for Large-Scale Instances

Solution Methods for General Quadratic Programming Problem with Continuous and Binary Variables: Overview

Explore related subjects.

Artificial Intelligence

Abbass HA (2001) MBO: marriage in honey bees optimization—a haplometrosis polygynous swarming approach. In: Proceedings of the congress on evolutionary computation, vol 1, pp 207–214

Abdel-Baset M, Hezam I (2016a) Cuckoo search and genetic algorithm hybrid schemes for optimization problems. Appl Math 10(3):1185–1192

Google Scholar

Abdel-Baset M, Hezam IM (2016b) Solving linear least squares problems based on improved cuckoo search algorithm. Math Sci 5(2):199–202

Abdel-Basset M, Hessin AN, Abdel-Fatah L (2016) A comprehensive study of cuckoo-inspired algorithms. Neural Comput Appl 29(2):345–361

Article Google Scholar

Abderrahim IA, Loukil L (2017) Hybrid PSO-TS approach for solving the quadratic three-dimensional assignment problem. In: 2017 IEEE international conference on embedded and distributed systems (EDiS), pp 1–5

Abreu NMM, Boaventura-Netto PO, Querido TM, Gouvêa EF (2002) Classes of quadratic assignment problem instances: isomorphism and difficulty measure using a statistical approach. Discret Appl Math 124(1–3):103–116

Article MathSciNet MATH Google Scholar

Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser Discret Math Theor Comput Sci 16:43–75

Ahyaningsih F (2017) A combined strategy for solving quadratic assignment problem. In: Proceedings of AIP conference, vol 1867, no 1, p 020006

Alatas B (2011) ACROA: artificial chemical reaction optimization algorithm for global optimization. Expert Syst Appl 38(10):13170–13180

Angel E, Zissimopoulos V (2000) On the classification of NP-complete problems in terms of their correlation coefficient. DAMATH Discret Appl Math Comb Oper Res Comput Sci 99(1–3):261–277

MathSciNet MATH Google Scholar

Angel E, Zissimopoulos V (2001) On the landscape ruggedness of the quadratic assignment problem. Theor Comput Sci 263(1–2):159–172

Angel E, Zissimopoulos V (2002) On the hardness of the quadratic assignment problem with metaheuristics. J Heuristics 8(4):399–414

Anstreicher KM (2003) Recent advances in the solution of quadratic assignment problems. Math Program 97(1):27–42

Anstreicher KM, Brixius NW (2001) A new bound for the quadratic assignment problem based on convex quadratic programming. Math Program 89(3):341–357

Arkin EM, Hassin R, Sviridenko M (2001) Approximating the maximum quadratic assignment problem. Inf Process Lett 77(1):13–16

Askarzadeh A, Rezazadeh A (2013) A new heuristic optimization algorithm for modeling of proton exchange membrane fuel cell: bird mating optimizer. Int J Energy Res 37(10):1196–1204

Azarbonyad H, Babazadeh R (2014) A genetic algorithm for solving quadratic assignment problem (QAP). arXiv preprint. http://arxiv.org/abs/1405.5050

Battiti R, Tecchiolli G (1994a) The reactive tabu search. ORSA J Comput 6(2):126–140

Article MATH Google Scholar

Baykasoglu A (2004) A metaheuristic algorithm to solve quadratic assignment formulations of cell formation problems without presetting number of cells. J Intell Manuf 15(6):753–759

Bazaraa MS, Elshafei AN (1979) An exact branch-and-bound procedure for the quadratic assignment problem. Nav Res Logist Q 26:109–121

Bazaraa MS, Kirca O (1983) A branch-and-bound based heuristic for solving the quadratic assignment problem. Nav Res Logist Q 30:287–304

Bazaraa MS, Sherali HD (1979) New approaches for solving the quadratic assignment problem. Oper Res Verfahr 32:29–46

Bazaraa MS, Sherali HD (1982) On the use of exact and heuristic cutting plane methods for the quadratic assignment problem. J Oper Res Soc 11:991–1003

Ben-David G, Malah D (2005) Bounds on the performance of vector-quantizers under channel errors. IEEE Trans Inf Theory 51(6):2227–2235

Benjaafar S (2002) Modeling and analysis of congestion in the design of facility layouts. Manag Sci 48(5):679–704

Benlic U, Hao JK (2013) Breakout local search for the quadratic assignment problem. Appl Math Comput 219(9):4800–4815

Bermudez R, Cole MH (2001) A genetic algorithm approach to door assignments in breakbulk terminals (No. MBTC 1084). University of Arkansas, Mack-Blackwell National Rural Transportation Study Center, Fayetteville

Blanchard A, Elloumi S, Faye A, Wicker N (2003) A cutting algorithm for the quadratic assignment problem. INFOR 41(1):35–49

Bland JA, Dawson GP (1994) Large-scale layout of facilities using a heuristic hybrid algorithm. Appl Math Model 18(9):500–503

Bölte A, Thonemann UW (1996) Optimizing simulated annealing schedules with genetic programming. Eur J Oper Res 92(2):402–416

Bos J (1993b) Zoning in forest management: a quadratic assignment problem solved by simulated annealing. J Environ Manag 37:127–145‏

Bousonocalzon C, Manning MRW (1995) The Hopfield neural-network applied to the quadratic assignment problem. Neural Comput Appl 3(2):64–72

Brixius NW, Anstreicher KM (2004) The Steinberg wiring problem. In: Grötschel M (ed) The sharpest cut: the impact of Manfred Padberg and his work. Society for Industrial and Applied Mathematics, Philadelphia, pp 293–307

Chapter Google Scholar

Brüngger A, Marzetta A, Clausen J, Perregaard M (1997) Joining forces in solving large-scale quadratic assignment problems. In: Proceedings of the 11th International parallel processing symposium IPPS. IEEE Computer Society Press, Los Alamitos, pp 418–427

Brüngger A, Marzetta A, Clausen J, Perregaard M (1998) Solving large-scale QAP problems in parallel with the search library ZRAM. J Parallel Distrib Comput 50(1–2):157–169

Brusco MJ, Stahl S (2000) Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. J Classif 17(2):197–223

Bukard RE, Offermann J (1977) Design of typewriter keyboards by means of quadratic assignment problems. J Oper Res 21(4):B121–B132

Burkard RE (2002) Selected topics on assignment problems. Discret Appl Math 123(1):257–302

Burkard RE, Bonniger T (1983) A heuristic for quadratic Boolean programs with applications to quadratic assignment problems. Eur J Oper Res 13:374–386

Burkard RE, Karisch SE, Rendl F (1997) QAPLIB—a quadratic assignment problem library. J Glob Optim 10(4):391–403‏

Cela E, Deineko V, Woeginger GJ (2017) New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices. Eur J Oper Res 267(3):818–834

Çela E (2002) Assignment problems. Handbook of applied optimization, pp 661–678

Chan Y, Francis RL, McGinnis LF, White JA (1993) Facility layout and location: an analytical approach

Chmiel W, Szwed P (2016) Bees algorithm for the quadratic assignment problem on CUDA platform. In: Gruca A, Brachman A, Kozielski S, Czachórski T (eds) Man–machine interactions, vol 391. Springer, Cham

Chmiel W, Kadłuczka P, Packanik G (2009) Performance of swarm algorithms for permutation problems. Automatyka 15(2):117–126‏

Chmiel W, Kadłuczka P, Kwiecień J, Filipowicz B (2017) A comparison of nature inspired algorithms for the quadratic assignment problem. Bull Pol Acad Sci Tech Sci 65(4):513–522

Chrétienne P (1989) A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. Eur J Oper Res 43(2):225–230

Christofides N, Benavent E (1989) An exact algorithm for the quadratic assignment problem. Oper Res 37(5):760–768

Ciriani V, Pisanti N, Bernasconi A (2004) Room allocation: a polynomial subcase of the quadratic assignment problem. Discret Appl Math 144(3):263–269

Colorni A, Dorigo M, Maffioli F, Maniezzo V, Righini G, Trubian M (1996) Heuristics from nature for hard combinatorial optimization problems. Int Trans Oper Res 3(1):1–21

Commander CW (2005) A survey of the quadratic assignment problem, with applications

Cung VD, Mautor T, Michelon P, Tavares A (1997) A scatter search based approach for the quadratic assignment problem. In: Proceedings of IEEE international conference on evolutionary computation, pp 165–169

Deineko VG, Woeginger GJ (2000) A study of exponential neighborhoods for the traveling salesman problem and for the quadratic assignment problem. Math Program Ser A 78:519–542

MATH Google Scholar

Dell’Amico M, Díaz JCD, Iori M, Montanari R (2009) The single-finger keyboard layout problem. Comput Oper Res 36(11):3002–3012

Dickey JW, Hopkins JW (1972) Campus building arrangement using TOPAZ. Transp Res 6(1):59–68

Dokeroglu T, Cosar A (2016) A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem. Eng Appl Artif Intell 52:10–25

Dorigo M (1992) Optimization learning and natural algorithms. PhD Thesis, Politecnico di Milano

Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26(2):29–41

Drezner Z (1995) Lower bounds based on linear programming for the quadratic assignment problem. Comput Optim Appl 4(2):159–165

Drezner Z (2005a) Compounded genetic algorithms for the quadratic assignment problem. Oper Res Lett 33(5):475–480

Drezner Z (2005b) The extended concentric tabu for the quadratic assignment problem. Eur J Oper Res 160:416–422

Drezner Z, Hahn PM, Taillard ÉD (2005) Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann Oper Res 139(1):65–94‏

Du H, Wu X, Zhuang J (2006) Small-world optimization algorithm for function optimization. In: International conference on natural computation. Springer, Berlin, pp 264–273

Durkota K (2011) Implementation of a discrete firefly algorithm for the QAP problem within the sage framework. Bachelor Thesis, Czech Technical University

Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on machine and human science (MHS), pp 39–43

Edwards CS (1980) A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem. In: Rayward-Smith VJ (eds) Combinatorial optimization II, vol 13. Springer, Berlin, Heidelberg

Eiselt HA, Laporte G (1991) A combinatorial optimization problem arising in dartboard design. J Oper Res Soc 42:113–118

El-Baz MA (2004) A genetic algorithm for facility layout problems of different manufacturing environments. Comput Ind Eng 47(2–3):233–246

Elshafei AN (1977) Hospital layout as a quadratic assignment problem. J Oper Res Soc 28(1):167–179

Erdoğan G, Tansel B (2007) A branch-and-cut algorithm for quadratic assignment problems based on linearization. Comput Oper Res 34(4):1085–1106

Erol OK, Eksin I (2006) A new optimization method: big bang–big crunch. Adv Eng Softw 37(2):106–111

Euler R, Le Verge H (1996) Time-tables, polyhedra and the greedy algorithm. Discret Appl Math 65(1–3):207–221

Fedjki CA, Duffuaa SO (2004) An extreme point algorithm for a local minimum solution to the quadratic assignment problem. Eur J Oper Res 156(3):566–578

Feizi S, Quon G, Recamonde-Mendoza M, Medard M, Kellis M, Jadbabaie A (2016) Spectral alignment of graphs. arXiv preprint. http://arxiv.org/abs/1602.04181 ‏

Ferreira JFB, Khoo Y, Singer A (2018) Semidefinite programming approach for the quadratic assignment problem with a sparse graph. Comput Optim Appl 69(3):677–712

Finke G, Burkard RE, Rendl F (1987) Quadratic assignment problems. Ann Discret Math 31:61–82

Fischetti M, Monaci M, Salvagnin D (2012) Three ideas for the quadratic assignment problem. Oper Res 60(4):954–964

Fogel LJ, Owens AJ, Walsh MJ (1966) Artificial intelligence through simulated evolution

Formato RA (2007) Central force optimization. Prog Electromagn Res 77:425–491

Francisco RB, Costa MFP, Rocha AMA (2014) Experiments with firefly algorithm. In: International conference on computational science and its applications. Springer, Cham, pp 227–236

Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discret Appl Math 5(1):89–98‏

Gabrielsson S (2008) A parallel tabu search algorithm for the quadratic assignment problem

Gallo G, Simeone B (1991) Optimal grouping of researchers into departments. Ricerca Operativa 57:64–69

Gambardella LM, Taillard D, Dorigo M (1999) Ant colonies for the QAP. J Oper Res Soc 50:167–176

Gandomi AH, Alavi AH (2012) Krill herd: a new bio-inspired optimization algorithm. Commun Nonlinear Sci Numer Simul 17(12):4831–4845

Gandomi AH, Yang XS, Alavi AH (2013) Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng Comput 29(1):17–35

Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. In: A series of books in the mathematical sciences

Gavett JW, Plyter NV (1966) The optimal assignment of facilities to locations by branch and bound. Oper Res 14:210–232

Geoffrion AM, Graves GW (1976) Scheduling parallel production lines with changeover costs: practical application of a quadratic assignment/LP approach. Oper Res 24(4):595–610

Ghandeshtani KS, Seyedkashi N, Mollai N, Neshati MM (2010) New simulated annealing algorithm for quadratic assignment problem. In: The fourth international conference on advanced engineering computing and applications in sciences, pp 87–92

Gharibi W, Xia Y (2010) New heuristic rounding approaches to the quadratic assignment problem. J Commun Comput 7(4):65‏

Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J Appl Math 10:305–313

Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166

Glover F (1989a) Tabu search. ORSA J Comput Part 1 1(3):190–206

Glover F (1989b) Tabu search. ORSA J Comput Part 2 1:4–32

Gonçalves AD, Pessoa AA, Bentes C, Farias R, Drummond LMDA. (2017) A graphics processing unit algorithm to solve the quadratic assignment problem using level-2 reformulation-linearization technique. INFORMS J Comput 29(4):676–687

Article MathSciNet Google Scholar

Gong D, Yamazaki G, Gen M, Xu W (1999) A genetic algorithm method for one dimensional machine location problems. Int J Prod Econ 60(1):337–342

Grötschel M (1992) Discrete mathematics in manufacturing. In: ICIAM91: proceedings of the second international conference on industrial and applied mathematics (SIAM), pp 119–145

Gutin G, Karapetyan D (2009) A memetic algorithm for the multidimensional assignment problem. In: International workshop on engineering stochastic local search algorithms. Springer, Berlin, pp 125–129

Gutin G, Yeo A (2002) Polynomial approximation algorithms for TSP and QAP with a factorial domination number. Discret Appl Math 119(1–2):107–116

Hadley SW, Rendl F, Wolkowicz H (1990) Bounds for the quadratic assignment problem using continuous optimization techniques. In: Proceedings of 1st international integer programming and combinatorial optimization conference (IPCO), pp 237–248

Hadley SW, Rendl F, Wolkowicz H (1993) A new lower bound via projection for the quadratic assignment problem. Math Oper Res 17:727–739

Hahn P, Grant T (1998) Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper Res 46:912–922

Hahn PM, Krarup J (2001) A hospital facility layout problem finally solved. J Intell Manuf 12(5):487–496

Hahn P, Grant T, Hall N (1998) A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. Eur J Oper Res 108:629–640

Hahn PM, Hightower WL, Johnson TA, Guignard-Spielberg M, Roucairol C (2001b) A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Working Paper 01-04, Systems Engineering Department, University of Pennsylvania

Hahn PM, Kim BJ, Hightower WL, Stützle T, Kanthak S, Samra H, Ding Z, Guignard M (2004) The quadratic three-dimensional assignment problem: exact and heuristic solution methods. OPIM Working Report No. 04-08-02, The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania, USA

Hahn PM, Zhu YR, Guignard M, Hightower WL, Saltzman MJ (2012) A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J Comput 24(2):202–209

Hannan E, McKeon P (1979) Matching swimmers to events in a championship swimming meet. Comput Oper Res 6(4):225–231

Hansen P, Lih KW (1992) Improved algorithms for partitioning problems in parallel, pipelined, and distributed computing. IEEE Trans Comput 41(6):769–771

Hansen N, Müller SD, Koumoutsakos P (2003) Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol Comput 11(1):1–18

Hasegawa M, Ikeguchi T, Aihara K, Itoh K (2002) A novel chaotic search for quadratic assignment problems. Eur J Oper Res 139(3):543–556

Hassin R, Levin A, Sviridenko M (2009) Approximating the minimum quadratic assignment problems. ACM Trans Algorithms (TALG) 6(1):18

Hatamlou A (2013) Black hole: a new heuristic optimization approach for data clustering. Inf Sci 222:175–184

Hezam IM, Abd-ElBaset M, Selem I (2015) Cuckoo search algorithm for stellar population analysis of galaxies. Int J Inf Technol Comput Sci 7:29–33

Holland JH (1992) Genetic algorithms. Sci Am 267(1):66–73

Huang G, Lim A (2006) A hybrid genetic algorithm for the three-index assignment problem. Eur J Oper Res 172(1):249–257

Hubert L (1986) Assignment methods in combinational data analysis, vol 73. CRC Press, Boca Raton

Hussain Ahmed Z (2018) A hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem. Cogent Eng. https://doi.org/10.1080/23311916.2018.1423743

Ignizio JP (1982) Linear programing in single and multiple objective systems. Prentice-Hall, Englewood Cliff

Ismail MM, Hezam IM, El-Sharkawy E (2017) Enhanced cuckoo search algorithm with SPV rule for quadratic assignment problem. Int J Comput Appl 158(4):39–42

Ji P, Wu Y, Liu H (2006) A solution method for the quadratic assignment problem (QAP). In: The sixth international symposium on operations research and its applications (ISORA), Xinjiang, China, August, pp 8–12

Jiang H, Zhang S, Ren Z, Lai X, Piao Y (2014) Approximate muscle guided beam search for three-index assignment problem. In: International conference in swarm intelligence. Springer, Cham, pp 44–52

Jünger M, Kaibel V (2000) On the SQAP-polytope. SIAM J Optim 11(2):444–463

Jünger M, Kaibel V (2001a) The QAP-polytope and the star transformation. Discret Appl Math 111(3):283–306

Jünger M, Kaibel V (2001b) Box-inequalities for quadratic assignment polytopes. Math Program 91(1):175–197

Kaibel V (1998) Polyhedral combinatorics of quadratic assignment problems with less objects than locations. In: Bixby RE, Boyd EA, Ríos-Mercado RZ (eds) Integer programming and combinatorial optimization, vol 1412. Springer, Berlin, Heidelberg

Karisch SE, Rendl F, Wolkowicz H (1994) Trust regions and relaxations for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS series in discrete mathematics and theoretical computer science, vol 16. AMS, Providence, pp 199–219

Karisch S, Çela E, Clausen J, Espersen T (1999) A dual framework for lower bounds of the quadratic assignment problem based on linearization. Computing 63:351–403

Kaufman L, Broeckx F (1978) An algorithm for the quadratic assignment problem using Bender’s decomposition. Eur J Oper Res 2(3):207–211

Kaveh A, Khayatazad M (2012) A new meta-heuristic method: ray optimization. Comput Struct 112:283–294

Kaveh A, Talatahari S (2010) A novel heuristic optimization method: charged system search. Acta Mech 213(3–4):267–289

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of international conference on neural network, vol 4. IEEE Service Center, Piscataway, pp 1942–1948

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680

Knowles JD, Corne D (2002) Towards landscape analyses to inform the design of hybrid local search for the multiobjective quadratic assignment problem. HIS 87:271–279

Knowles J, Corne D (2003) Instance generators and test suites for the multiobjective quadratic assignment problem. In: International conference on evolutionary multi-criterion optimization. Springer, Berlin, pp 295–310

Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econom J Econom Soc 25(1):53–76

Koza JR (1992) Genetic programming II, automatic discovery of reusable subprograms. MIT Press, Cambridge

Krarup J, Pruzan PM (1978) Computer-aided layout design. Mathematical programming in use, pp 75–94

Kreher DL, Stinson DR (1998) Combinatorial algorithms: generation, enumeration, and search, vol 7. CRC Press, Boca Raton

Lawler EL (1963) The quadratic assignment problem. Manag Sci 9(4):586–599

Li XL (2003) A new intelligent optimization-artificial fish swarm algorithm. Doctor Thesis, Zhejiang University of Zhejiang, China

Li Y, Pardalos PM, Ramakrishnan KG, Resende MG (1994) Lower bounds for the quadratic assignment problem. Ann Oper Res 50(1):387–410

Liu H, Abraham A, Zhang J (2007) A particle swarm approach to quadratic assignment problems. In: Saad A, Dahal K, Sarfraz M, Roy R (eds) Soft computing in industrial applications, vol 39. Springer, Berlin, Heidelberg

Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T (2007) A survey for the quadratic assignment problem. Eur J Oper Res 176(2):657–690

Loukil L, Mehdi M, Melab N, Talbi EG, Bouvry P (2009) A parallel hybrid genetic algorithm-simulated annealing for solving Q3AP on computational grid. In: 2009 IEEE international symposium on IEEE parallel and distributed processing (IPDPS), pp 1–8

Lu X, Zhou Y (2008) A novel global convergence algorithm: bee collecting pollen algorithm. In: International conference on intelligent computing. Springer, Berlin, pp 518–525

Machol RE (1970) An application of the assignment problem. Oper Res 18(4):745–746

Maniezzo V (1999) Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS J Comput 11(4):358–369

Maniezzo V, Colorni A (1995) Algodesk: an experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem. Eur J Oper Res 81(1):188–204

Maniezzo V, Colorni A (1999) The ant system applied to the quadratic assignment problem. Knowl Data Eng 11(5):769–778

Mans B, Mautor T, Roucairol C (1995) A parallel depth first search branch and bound algorithm for the quadratic assignment problem. Eur J Oper Res 81:617–628

Marins MTA, Abreu NMM, Jurkiewicz S (2004) Auto morphism of groups and quadratic assignment problem. In: 2004 Annals of XII Congreso Latino-Iberoamericano de Investigación de Operaciones y Sistemas (CLAIO). La Habana, Cuba

Mason A, Rönnqvist M (1997) Solution methods for the balancing of jet turbines. Comput Oper Res 24(2):153–167

Mavridou T, Pardalos PM, Pitsoulis LS, Resende MGC (1998) A GRASP for the biquadratic assignment problem. Eur J Oper Res 105(3):613–621

Middendorf M, Reischle F, Schmeck H (2002) Multi colony ant algorithms. J Heuristics 8(3):305–320

Milis LZ, Magirou VF (1995) A Lagrangian-relaxation algorithm for sparse quadratic assignment problems. Oper Res Lett 17(2):69–76

Mills P, Tsang E, Ford J (2003) Applying an extended guided local search to the quadratic assignment problem. Ann Oper Res 118(1–4):121–135

Miranda G, Luna HPL, Mateus GR, Ferreira RPM (2005) A performance guarantee heuristic for electronic components placement problems including thermal effects. Comput Oper Res 32(11):2937–2957‏

Misevicius A (2000a) An intensive search algorithm for the quadratic assignment problem. Informatica 11:145–162

Misevicius A (2000b) A new improved simulated annealing algorithm for the quadratic assignment problem. Inf Technol Control 17:29–38

Misevicius A (2001) Combining simulated annealing and tabu search for the quadratic assignment problem. Inf Technol Control 20:37–50

Misevicius A (2003) A modified simulated annealing algorithm for the quadratic assignment problem. Informatica 14(4):497–514

Misevicius A (2004a) An improved hybrid optimization algorithm for the quadratic assignment problem. Math Model Anal 9(2):149–168

Misevicius A (2004b) An improved hybrid genetic algorithm: new results for the quadratic assignment problem. Knowl Based Syst 17(2–4):65–73

Mittelmann HD, Salvagnin D (2015) On solving a hard quadratic 3-dimensional assignment problem. Math Program Comput 7(2):219–234

Mladenovi N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100

Moghaddam FF, Moghaddam RF, Cheriet M (2012) Curved space optimization: a random search based on general relativity theory. arXiv preprint. http://arxiv.org/abs/1208.2214

Mucherino A, Seref O (2007) Monkey search: a novel metaheuristic search for global optimization. In: AIP conference proceedings, vol 953, no 1, pp 162–173

Munera D, Diaz D, Abreu S (2016a) Hybridization as cooperative parallelism for the quadratic assignment problem. In: International workshop on hybrid metaheuristics. Springer, Cham, pp 47–61

Munera D, Diaz D, Abreu S (2016b) Solving the quadratic assignment problem with cooperative parallel extremal optimization. In: European conference on evolutionary computation in combinatorial optimization. Springer, Cham, pp 251–266

Mzili I, Riffi ME, Benzekri F (2017) Penguins search optimization algorithm to solve quadratic assignment problem. In: Proceedings of the 2nd international conference on big data, cloud and applications, ACM, New York, p 20

Nishiyama T, Tsuchiya K, Tsujita K (2001) A Markov chain Monte Carlo algorithm for the quadratic assignment problem based on replicator equations. In: Proceedings of the artificial neural networks (ICANN). Lecture notes in computer science, vol 2130, pp 148–155

Nissen V, Paul H (1995) A modification of threshold accepting and its application to the quadratic assignment problem. Oper Res Spektrum 17(2–3):205–210

Nyberg A (2014) Some reformulations for the quadratic assignment problem

Oliveira CAS, Pardalos MP, Resende MGG (2004) GRASP with path relinking for the quadratic assignment problem. In: Ribeiro CC, Martins SL (eds) Experimental and efficient algorithms, vol 3059. Springer, Berlin, Heidelberg

Omidbakhsh M, Seifbarghy M (2011) Solving quadratic assignment problem (QAP) using invasive weed optimization algorithm. J Ind Eng (Special Issue):113–125

Özçetin E, Öztürk G (2016) A hybrid genetic algorithm for the quadratic assignment problem on graphics processing units. Anadolu Univ J Sci Technol Appl Sci Eng 17(1):167–180

Ozturk ZK, Uluel M (2017) A hybrid NSGA-II algorithm for multiobjective quadratic assignment problems. Acta Phys Pol A 132(3):959–962

Padberg W, Rijal P (1996) Location, scheduling, design and integer programming. In: International series in operations research management science. Operations research, vol 150, p 02803

Padberg MW, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33:60–100

Pan WT (2012) A new fruit fly optimization algorithm: taking the financial distress model as an example. Knowl Based Syst 26:69–74

Paquete L, Stützle T (2006) A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices. Eur J Oper Res 169(3):943–959

Pardalos L, Resende M (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Quadratic assignment and related problems. DIMACS series on discrete mathematics and theoretical computer science, vol 16, pp 237–261

Pardalos PM, Wolkowicz H (1994) Quadratic assignment and related problems. In: DIMACS workshop, vol 16, American Mathematical Society (AMS), Providence, pp 117–146

Pardalos PM, Rendl F, Wolkowitz H (1994) The quadratic assignment problem: a survey and recent developments. In: Quadratic assignment and related problem

Pardalos PM, Ramakrishnan KG, Resende MG, Li Y (1997) Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem. SIAM J Optim 7(1):280–294

Parker AW, Parker ME, Proll LG (1990) Constructing timetables for parent-teacher interviews: a practical scheduling problem. University of Leeds, Department of Computer Studies, Leeds

Phillips AT, Rosen JB (1994) A quadratic assignment formulation of the molecular conformation problem. J Glob Optim 4(2):229–241

Pierskalla WP (1967a) The tri-substitution method for the three-dimensional assignment problem. CORS J 5(2):71–81

Pierskalla WP (1967b) The multi-dimensional assignment and quadratic assignment problems. In: Technical memorandum no. 93. Case Western Reserve University, Operations Research Department, School of Management, Cleveland, OH

Pierskalla WP (1968) Letter to the editor—the multidimensional assignment problem. Oper Res 16(2):422–431

Pinto PC, Runkler TA, Sousa JM (2007) Wasp swarm algorithm for dynamic MAX-SAT problems. In: International conference on adaptive and natural computing algorithms. Springer, Berlin, pp 350–357

Pitsoulis LS, Pardalos PM, Hearn DW (2001) Approximate solutions to the turbine balancing problem. Eur J Oper Res 130(1):147–155

Pollatschek MA, Gershoni N, Radday YT (1976) Optimization of the typewriter keyboard by simulation. Angewandte Informatik 17:438–439

Pradeepmon TG, Panicker VV, Sridharan R (2016) Parameter selection of discrete particle swarm optimization algorithm for the quadratic assignment problems. Procedia Technol 25:998–1005

QAPLIB (2017) A quadratic assignment problem library [on line]. http://anjos.mgi.polymtl.ca/qaplib/news.htm . Accessed 6 Aug 2017

Ramakrishnan KG, Resende MGC, Pardalos PM (1996) A branch and bound algorithm for the quadratic assignment problem using a lower bound based on linear programming. In: Floudas CA, Pardalos PM (eds) State of the art in global optimization. Nonconvex optimization and its applications, vol 7. Springer, Boston, MA

Ramakrishnan KG, Resende MGC, Ramachandran B, Pekny JF (2002) Tight QAP bounds via linear programming. In: Combinatorial and global optimization. World Scientific Publishing, Singapore, pp 297–303. https://doi.org/10.1142/9789812778215_0019

Rashedi E, Nezamabadi-Pour H, Saryazdi S (2009) GSA: a gravitational search algorithm. Inf Sci 179(13):2232–2248

Rendl F, Sotirov R (2007) Bounds for the quadratic assignment problem using the bundle method. Math Program 109(2–3):505–524

Rendl F, Wolkowicz H (1992) Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem. Math Program 53:63–78

Reynolds AM, Frye MA (2007) Free-flight odor tracking in Drosophila is consistent with an optimal intermittent scale-free search. PloS One 2(4):e354

Riffi ME, Sayoti F (2017) Hybrid algorithm for solving the quadratic assignment problem. Int J Interact Multimed Artif Intell. https://doi.org/10.9781/ijimai.2017.10.003

Roth M (2005) Termite: a swarm intelligent routing algorithm for mobile wireless ad-hoc networks

Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565‏

Sanhueza C, Jiménez F, Berretta R, Moscato P (2017) PasMoQAP: a parallel asynchronous memetic algorithm for solving the Multi-Objective Quadratic Assignment Problem. In: 2017 IEEE congress on evolutionary computation (CEC), pp 1103–1110

Schulz C, Träff JL (2017) Better process mapping and sparse quadratic assignment. arXiv preprint. http://arxiv.org/abs/1702.04164

Shah-Hosseini H (2011) Principal components analysis by the galaxy-based search algorithm: a novel metaheuristic for continuous optimization. Int J Comput Sci Eng 6(1–2):132–140

Shi Y, Eberhart R (1998) A modified particle swarm optimizer. In: Proceedings of IEEE world congress on computational intelligence, pp 69–73

Shilane D, Martikainen J, Dudoit S, Ovaska SJ (2008) A general framework for statistical performance comparison of evolutionary computation algorithms. Inf Sci 178(14):2870–2879‏

Shiqin Y, Jianjun J, Guangxing Y (2009) A dolphin partner optimization. In: 2009 WRI global congress on intelligent systems (GCIS), vol 1, pp 124–128‏

Shylo PV (2017) Solving the quadratic assignment problem by the repeated iterated tabu search method. Cybern Syst Anal 53(2):308–311

Simon D (2008) Biogeography-based optimization. IEEE Trans Evol Comput 12(6):702–713

Siu F, Chang RKC (2002) Effectiveness of optimal node assignments in wavelength division multiplexing networks with fixed regular virtual topologies. Comput Netw 38(1):61–74

Skorin-Kapov J (1990) Tabu search applied to the quadratic assignment problem. ORSA J Comput 2(1):33–45

Smith M, Li W (2001) Quadratic assignment problems and M/G/C/C/ state dependent network flows. J Comb Optim 5:421–444

Solimanpur M, Vrat P, Shankar R (2004) Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. Eur J Oper Res 157(3):592–606

Steinberg L (1961) The backboard wiring problem: a placement algorithm. SIAM Rev 3(1):37–50

Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11(4):341–359

Syed-Abdullah SS, Abdul-Rahman S, Benjamin AM, Wibowo A, Ku-Mahamud KR (2018) Solving quadratic assignment problem with fixed assignment (QAPFA) using branch and bound approach. In: IOP conference series: materials science and engineering, vol 300, no 1, p 012002

Taillard É (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17(4–5):443–455

Talbi EG, Roux O, Fonlupt C, Robillard D (2001) Parallel ant colonies for the quadratic assignment problem. Future Gener Comput Syst 17(4):441–449

Tseng LY, Liang SC (2005) A hybrid metaheuristic for the quadratic assignment problem. Comput Optim Appl 34:85–113

Tsutsui S (2008) Parallel ant colony optimization for the quadratic assignment problems with symmetric multi-processing. In: International conference on ant colony optimization and swarm intelligence. Springer, Berlin, pp 363–370

Ugi I, Bauer J, Brandt J, Friedrich J, Gasteiger J, Jochum C, Schubert W (1979) New fields of application for computers in chemistry. Angew Chem 91(2):99–111

Uwate Y, Nishio Y, Ushida A (2004) Markov chain modeling of intermittency chaos and its application to Hopfield NN. IEICE Trans Fundam Electron Commun Comput Sci 87(4):774–779

Inoba V, Indhumathi A (2015) A study on quadratic assignment problem in wireless sensor networks. Int J Latest Trends Eng Technol (IJLTET) 6(1):30–36

Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, … Priebe CE (2015) Fast approximate quadratic programming for graph matching. PLOS One 10(4):e0121002

Wang RL, Okazaki K (2005) Solving facility layout problem using an improved genetic algorithm. IEICE Trans Fundam Electron Commun Comput Sci 88(2):606–610

Webster B, Bernhard PJ (2003) A local search optimization algorithm based on natural principles of gravitation

Wess B, Zeitlhofer T (2004) On the phase coupling problem between data memory layout generation and address pointer assignment. In: Schepers H (eds) Software and compilers for embedded systems, vol 3199. Springer, Berlin, Heidelberg

Chapter MATH Google Scholar

White DJ (1995) Some concave-convex representations of the quadratic assignment problem. Eur J Oper Res 80(2):418–424

Wilhelm MR, Ward TL (1987) Solving quadratic assignment problems by simulated annealing. IIE Trans 19(1):107–119

Wolkowicz H (2000) Semidefinite programming approaches to the quadratic assignment problem. In: Pardalos PM, Pitsoulis LS (eds) Nonlinear assignment problems. Combinatorial Optimization, vol 7. Springer, Boston, MA

Wolkowicz H, Saigal R, Vandenberghe L (2000) Handbook of semidefinite programming: theory, algorithms, and applications, vol 27. Springer Science and Business Media, Berlin

Book MATH Google Scholar

Wolkowicz H (2010) Generating eigenvalue bounds using optimization. In: Pardalos P, Rassias T, Khan A (eds) Nonlinear analysis and variational problems, vol 35. Springer, New York, NY

Xia Y (2008) Gilmore-Lawler bound of quadratic assignment problem. Front Math China 3(1):109–118

Yamada S (1992) A new formulation of the quadratic assignment problem on r -dimensional grid. IEEE Trans Circuits Syst I Fundam Theory Appl 39(10):791–797

Yang XS (2010) Firefly algorithm, stochastic test functions and design optimization. Int J Bio Inspired Comput 2(2):78–84‏

Yang XS, Deb S (2009) Cuckoo search via Lévy flights. In: 2009 IEEE world congress on nature and biologically inspired computing (NaBIC), pp 210–214

Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3(2):82–102

Ying KC, Liao CJ (2004) An ant colony system for permutation flow-shop sequencing. Comput Oper Res 31(5):791–801

Youssef H, Sait SM, Ali H (2003) Fuzzy simulated evolution algorithm for VLSI cell placement. Comput Ind Eng 44(2):227–247

Yu J, Sarker BR (2003) Directional decomposition heuristic for a linear machine-cell location problem. Eur J Oper Res 149(1):142–184

Zaied ANH, Shawky LAEF (2014) A survey of quadratic assignment problems. Int J Comput Appl 101(6):28–36

Zhang R (2011) Quadratic bottleneck problems: algorithms, complexity and related topics. Doctoral dissertation, Science: Department of Mathematics

Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J Comb Optim 2:71–109

Zurada JM, Marks RJ, Robinson J (1995) Review of computational intelligence: imitating life

Download references

Author information

Authors and affiliations.

Department of Operations Research, Faculty of Computers and Informatics, Zagazig University, Zagazig, Egypt

Mohamed Abdel-Basset & Heba Rashad

University of California, Davis, United States

Gunasekaran Manogaran

Department of Information System, Faculty of Computers and Informatics, Zagazig University, Zagazig, Egypt

Abdel Nasser H. Zaied

You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohamed Abdel-Basset .

Additional information

Publisher’s note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Abdel-Basset, M., Manogaran, G., Rashad, H. et al. A comprehensive review of quadratic assignment problem: variants, hybrids and applications. J Ambient Intell Human Comput (2018). https://doi.org/10.1007/s12652-018-0917-x

Download citation

Received : 03 April 2018

Accepted : 13 June 2018

Published : 20 June 2018

DOI : https://doi.org/10.1007/s12652-018-0917-x

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Quadratic assignment problem
Formulations
Exact approaches
Heuristics approaches
Metaheuristic approaches
Find a journal
Publish with us
Track your research

IMAGES

PPT
GitHub
Introduction to NP Completeness. P and NP Problem
(PDF) A New Formulation of Quadratic Assignment Problem (QAP)
Introduction to NP-Complete Complexity Classes
NP, NP-Hard, NP-Complete, Circuit Satisfiability Problem

COMMENTS

Quadratic Assignment Problem (QAP) - GeeksforGeeks
The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them. The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.
Quadratic assignment problem - Wikipedia
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koopmans and Beckmann.
Quadratic Assignment Problems - SpringerLink
This chapter introduces quadratic assignment problems (QAP) as models for finding an optimal assignment among two sets of interrelated objects. References to many applications of QAPs, like in location theory, are given.
Quadratic Assignment Problem (QAP) - LightSolver
Imagine trying to determine the best positions for machines in a factory or servers in a data center, where the objective is to reduce the total cost of transporting materials or data between them. The QAP captures this real-world problem, seeking an optimal solution among the many possible layouts.
The Quadratic Assignment Problem - TU Graz
atic assignment problems (QAPs). It discusses the most important developments in all aspects of the QAP such as linearizations, QAP polyhedra, algorithms to solve the problem to optimality, heuristics, polynomially solvable specia.
Quadratic Assignment Problem - SpringerLink
The quadratic assignment problem is strongly NP-hard. For an arbitrary 𝜖 > 0 , the existence of a polynomial time 𝜖-approximation algorithm for the QAP implies P = NP. The proof is done by a reduction from the Hamiltonian cycle problem [ 58 ].
Lecture 3: Examples of NP-Complete Problems
problem is in NP since any assignment of values to variables can be veri ed in polynomial time. W. SAT. p 3SAT. We reduce each clause of the SAT instance containing more than 3 literals into a conjunction of several new clauses in 3SAT instance as follows:
A Solution Method for the Quadratic Assignment Problem (QAP)
Since QAP is NP-complete, it is notoriously difcult to be solved by exact solution methods. This paper focuses on the intelli- gent solution methods, particularly, genetic algorithms, and related development on QAP. A hybrid genetic algorithm is devised to examine the solvability of QAP instances.
A comprehensive review of quadratic assignment problem ...
The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields.

Quadratic Assignment Problem (QAP)

Similar Reads

What kind of Experience do you want to share?

Quadratic Assignment Problem (QAP)

Introduction

The Challenge: Real-time Assignments

Putting QUBO to work

Benchmark against Google OR-Tools Solvers

You may also like:

BOOK A DEMO

1. Acceptance of These Terms

2. The Site

3. Use Restrictions

4. Privacy Policy

5. License

6. Feedback

7. Intellectual Property Rights

8. Third Party Components

9. Availability

10. Changes to the Site

11. Disclaimer and Warranties

12. Limitation of Liability

13. Indemnification

14. Amendments to the Terms

16. General

17. Interpretation

18. Contact Us

LightSolver – Website Privacy Policy

1. Your Consent

2. Information We Collect

3. Methods of Information Collection

4. Purposes of Collection

5. Sharing Information With Third Parties

6. Modification or Deletion of Personal Information

8. Security

9. Third Party Software/ Services

10. Cookies & Local Storage

11. Where Do We Store User’s Personal Information?

12. Job Candidates

13. Updating, Obtaining a Copy of, or Deleting Your Personal Information

14. Direct Marketing

15. Changes to This Privacy Policy

16. Contact Us

Your message was submitted successfully

A comprehensive review of quadratic assignment problem: variants, hybrids and applications

Cite this article

Access this article

Similar content being viewed by others

Quadratic Assignment Problems

Metaheuristics with Local Search Miscellany Applied to the Quadratic Assignment Problem for Large-Scale Instances

Solution Methods for General Quadratic Programming Problem with Continuous and Binary Variables: Overview

Author information

Corresponding author

Additional information

Rights and permissions

About this article

Share this article

IMAGES

COMMENTS