quadratic assignment problem evaluation

Quadratic assignment problem

Author: Thomas Kueny, Eric Miller, Natasha Rice, Joseph Szczerba, David Wittmann (SysEn 5800 Fall 2020)

• 1 Introduction
• 2.1 Koopmans-Beckman Mathematical Formulation
• 2.2.1 Parameters
• 2.3.1 Optimization Problem
• 2.4 Computational Complexity
• 2.5 Algorithmic Discussions
• 2.6 Branch and Bound Procedures
• 2.7 Linearizations
• 3.1 QAP with 3 Facilities
• 4.1 Inter-plant Transportation Problem
• 4.2 The Backboard Wiring Problem
• 4.3 Hospital Layout
• 4.4 Exam Scheduling System
• 5 Conclusion
• 6 References

Introduction

The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957 [1] , is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, inter-plant transportation, hospital transportation, exam scheduling, along with many other applications not described within this page.

Theory, Methodology, and/or Algorithmic Discussions

Koopmans-beckman mathematical formulation.

Economists Koopmans and Beckman began their investigation of the QAP to ascertain the optimal method of locating important economic resources in a given area. The Koopmans-Beckman formulation of the QAP aims to achieve the objective of assigning facilities to locations in order to minimize the overall cost. Below is the Koopmans-Beckman formulation of the QAP as described by neos-guide.org.

Quadratic Assignment Problem Formulation

Inner Product

Note: The true objective cost function only requires summing entries above the diagonal in the matrix comprised of elements

Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value. See the Numerical Example section for an example of this note.

Optimization Problem

With all of this information, the QAP can be summarized as:

Computational Complexity

QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who states that of all combinatorial optimization problems, QAP is the “hardest of the hard”. [2]

Algorithmic Discussions

While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:

• Dynamic Program
• Cutting Plane

Branch and Bound Procedures

The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.

The Branch and Bound method was first proposed by Ailsa Land and Alison Doig in 1960 and is the most commonly used tool for solving NP-hard optimization problems.

A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before one lists all of the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and the branch is eliminated if it cannot produce a better solution than the best one found so far by the algorithm.

Linearizations

The first attempts to solve the QAP eliminated the quadratic term in the objective function of

in order to transform the problem into a (mixed) 0-1 linear program. The objective function is usually linearized by introducing new variables and new linear (and binary) constraints. Then existing methods for (mixed) linear integer programming (MILP) can be applied. The very large number of new variables and constraints, however, usually poses an obstacle for efficiently solving the resulting linear integer programs. MILP formulations provide LP relaxations of the problem which can be used to compute lower bounds.

Numerical Example

Qap with 3 facilities.

Applications

Inter-plant transportation problem.

The QAP was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations. [1] Factoring in the location of each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.

The Backboard Wiring Problem

As the QAP is focused on minimizing the cost of traveling from one location to another, it is an ideal approach to determining the placement of components in many modern electronics. Leon Steinberg proposed a QAP solution to optimize the layout of elements on a blackboard by minimizing the total amount of wiring required. [4]

When defining the problem Steinberg states that we have a set of n elements

as well as a set of r points

In his paper he derives the below formula:

In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation, he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.

The initial placement of components is shown below:

After the initial placement of elements, it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.

Hospital Layout

Building new hospitals was a common event in 1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem". [5] With the high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create an optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Outpatient ward was acting as a bottleneck in the hospital and focused his efforts on optimizing the 17 departments there.

Elshafei identified the following QAP to determine where clinics should be placed:

For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 based on the original hospital layout.

Exam Scheduling System

The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross-program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.” [6]

• ↑ 1.0 1.1 1.2 Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
• ↑ 2.0 2.1 Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem
• ↑ 3.0 3.1 3.2 Burkard, R. E., Çela, E., Pardalos, P. M., & Pitsoulis, L. S. (2013). The Quadratic Assignment Problem. https://www.opt.math.tugraz.at/~cela/papers/qap_bericht.pdf .
• ↑ 4.0 4.1 Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review . 1961;3(1):37.
• ↑ 5.0 5.1 Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977) . 1977;28(1):167. doi:10.2307/300878
• ↑ 6.0 6.1 Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.

Navigation menu

(Stanford users can avoid this Captcha by logging in.)

• Send to text email RefWorks EndNote printer

The Quadratic Assignment Problem : Theory and Algorithms

Available online.

• SpringerLink

More options

• Find it at other libraries via WorldCat
• Contributors

Description

Creators/contributors, contents/summary.

• Preface. List of Figures. List of Tables.
• 1. Problem Statement and Complexity Aspects.
• 2. Exact Algorithms and Lower Bounds.
• 3. Heuristics and Asymptotic Behavior.
• 4. QAPs on Specially Structured Matrices.
• 5. Two More Restricted Versions of the QAP.
• 6. QAPs Arising as Optimization Problems in Graphs.
• 7. On the Biquadratic Assignment Problem (BIQAP). References. Notation Index. Subject Index.
• (source: Nielsen Book Data)

Bibliographic information

• Stanford Home
• Maps & Directions
• Search Stanford
• Emergency Info
• Terms of Use
• Non-Discrimination
• Accessibility

© Stanford University , Stanford , California 94305 .

The Quadratic Assignment Problem

Theory and Algorithms

• © 1998
• Eranda Çela 0

Institute of Mathematics, Technical University Graz, Graz, Austria

You can also search for this author in PubMed   Google Scholar

Part of the book series: Combinatorial Optimization (COOP, volume 1)

3084 Accesses

179 Citations

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

Access this book

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

Similar content being viewed by others.

Quadratic Assignment Problems

Integer Programming

• Approximation
• Facility Location
• combinatorial optimization
• optimization
• combinatorics

Table of contents (7 chapters)

Front matter, problem statement and complexity aspects.

Eranda Çela

Exact Algorithms and Lower Bounds

Heuristics and asymptotic behavior, qaps on specially structured matrices, two more restricted versions of the qap, qaps arising as optimization problems in graphs, on the biquadratic assignment problem (biqap), back matter, authors and affiliations, bibliographic information.

Book Title : The Quadratic Assignment Problem

Book Subtitle : Theory and Algorithms

Authors : Eranda Çela

Series Title : Combinatorial Optimization

DOI : https://doi.org/10.1007/978-1-4757-2787-6

Publisher : Springer New York, NY

eBook Packages : Springer Book Archive

Copyright Information : Springer Science+Business Media Dordrecht 1998

Hardcover ISBN : 978-0-7923-4878-8 Published: 31 December 1997

Softcover ISBN : 978-1-4419-4786-4 Published: 08 December 2010

eBook ISBN : 978-1-4757-2787-6 Published: 14 March 2013

Series ISSN : 1388-3011

Edition Number : 1

Number of Pages : XV, 287

Topics : Optimization , Algorithms , Theory of Computation , Discrete Mathematics in Computer Science , Combinatorics

• Publish with us

Policies and ethics

• Find a journal
• Track your research

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

Imaginee 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

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.

You may also like:

Optimization: Rotor Blade Sorting for Jet Engines

Dr. Avigail Kaner

Field Service Technician Scheduling Optimization (EDCVRP)

Dr. Ilan Karpas

Sign up for updates

Get news and blog posts straight to your inbox!

I agree to receiving communications from LightSolver.

Follow our journey as we change the world of computation.

• News & Publications
• Book a Demo
• Terms of Use
• Privacy Policy
• Alon Tower 2
• Yigal Alon 94,
• Tel Aviv, Israel
• [email protected]

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

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

• 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.

Please Login to comment...

Similar reads.

• Top Android Apps for 2024
• Top Cell Phone Signal Boosters in 2024
• Best Travel Apps (Paid & Free) in 2024
• The Best Smart Home Devices for 2024
• 15 Most Important Aptitude Topics For Placements [2024]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• DOI: 10.1287/MNSC.27.4.442
• Corpus ID: 122644082

The Quadratic Assignment Problem: An Experimental Evaluation of Solution Strategies

• Published 1 April 1981
• Business, Mathematics
• Management Science

70 Citations

The quadratic assignment problem: an analysis of applications and solution strategies, a flexible, polynomial-time, construction and improvement heuristic for the quadratic assignment problem, an exact algorithm for the general quadratic assignment problem, an exact branch and bound algorithm for the general quadratic assignment problem, on the quality of heuristic solutions to a 19 × 19 quadratic assignment problem, the quadratic minimum spanning tree problem, a hybrid heuristic for the facilities layout problem, an improved heuristic for the quadratic assignment problem, resolution of quadratic assignment problems using an evolutionary algorithm, an improved annealing scheme for the qap, 11 references, suboptimal algorithms for the quadratic assignment problem, an algorithm for the quadratic assignment problem.

• Highly Influential

Quadratic Assignment Problem Algorithms and the Location of Indivisible Facilities

On predicting computational time of a branch and bound algorithm for the assignment of facilities, optimal and suboptimal algorithms for the quadratic assignment problem, the efficiency of computer algorithms for plant layout, the facilities layout problem in perspective, reducibility among combinatorial problems, comparison of computer algorithms and visual based methods for plant layout, the backboard wiring problem: a placement algorithm, related papers.

Showing 1 through 3 of 0 Related Papers

quadratic_assignment #

Approximates solution to the quadratic assignment problem and the graph matching problem.

Quadratic assignment solves problems of the following form:

where \(\mathcal{P}\) is the set of all permutation matrices, and \(A\) and \(B\) are square matrices.

Graph matching tries to maximize the same objective function. This algorithm can be thought of as finding the alignment of the nodes of two graphs that minimizes the number of induced edge disagreements, or, in the case of weighted graphs, the sum of squared edge weight differences.

Note that the quadratic assignment problem is NP-hard. The results given here are approximations and are not guaranteed to be optimal.

The square matrix \(A\) in the objective function above.

The square matrix \(B\) in the objective function above.

The algorithm used to solve the problem. ‘faq’ (default) and ‘2opt’ are available.

A dictionary of solver options. All solvers support the following:

Maximizes the objective function if True .

Fixes part of the matching. Also known as a “seed” [2] .

Each row of partial_match specifies a pair of matched nodes: node partial_match[i, 0] of A is matched to node partial_match[i, 1] of B . The array has shape (m, 2) , where m is not greater than the number of nodes, \(n\) .

numpy.random.RandomState }, optional

If seed is None (or np.random ), the numpy.random.RandomState singleton is used. If seed is an int, a new RandomState instance is used, seeded with seed . If seed is already a Generator or RandomState instance then that instance is used.

For method-specific options, see show_options('quadratic_assignment') .

OptimizeResult containing the following fields.

Column indices corresponding to the best permutation found of the nodes of B .

The objective value of the solution.

The number of iterations performed during optimization.

The default method ‘faq’ uses the Fast Approximate QAP algorithm [1] ; it typically offers the best combination of speed and accuracy. Method ‘2opt’ can be computationally expensive, but may be a useful alternative, or it can be used to refine the solution returned by another method.

J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, and C.E. Priebe, “Fast approximate quadratic programming for graph matching,” PLOS one, vol. 10, no. 4, p. e0121002, 2015, DOI:10.1371/journal.pone.0121002

D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, DOI:10.1016/j.patcog.2018.09.014

“2-opt,” Wikipedia. https://en.wikipedia.org/wiki/2-opt

The see the relationship between the returned col_ind and fun , use col_ind to form the best permutation matrix found, then evaluate the objective function \(f(P) = trace(A^T P B P^T )\) .

Alternatively, to avoid constructing the permutation matrix explicitly, directly permute the rows and columns of the distance matrix.

Although not guaranteed in general, quadratic_assignment happens to have found the globally optimal solution.

Here is an example for which the default method, ‘faq’ , does not find the global optimum.

If accuracy is important, consider using ‘2opt’ to refine the solution.