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

{\displaystyle F=(F_{ij})}

Inner Product

{\displaystyle A,B}

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

{\displaystyle F_{i,j}(X_{\phi }DX_{\phi }^{T})_{i,j}}

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:

{\displaystyle \min _{X\in P}\langle F,XDX^{T}\rangle }

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

{\displaystyle min\sum _{i=1}^{n}\sum _{j=1}^{n}c{_{\phi (i)\phi (j)}}+\sum _{i=1}^{n}b{_{\phi (i)}}}

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.

{\displaystyle D={\begin{bmatrix}0&5&6\\5&0&3.6\\6&3.6&0\end{bmatrix}}}

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

{\displaystyle E=\left\{E_{1},E_{2},...,E_{n}\right\}}

as well as a set of r points

{\displaystyle P_{1},P_{2},...,P_{r}}

In his paper he derives the below formula:

{\displaystyle min\sum _{1\leq i\leq j\leq n}^{}C_{ij}(d_{s(i)s(j))})}

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:

quadratic assignment problem fuzzy

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.

quadratic assignment problem fuzzy

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:

{\displaystyle min\sum _{i,j}\sum _{k,q}f_{ik}d_{jq}y_{ij}y_{kq}}

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]

{\displaystyle n!}

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

A Fuzzy Particle Swarm Approach to Multiobjective Quadratic Assignment Problems

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.

  • 90% Refund @Courses
  • Data Structure
  • Analysis of Algorithms
  • Backtracking
  • Dynamic Programming
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Pattern Searching
  • Bitwise Algorithms
  • Branch & Bound
  • Randomized Algorithms

Related Articles

  • Solve Coding Problems
  • Introduction to Exact Cover Problem and Algorithm X
  • Implementation of Exact Cover Problem and Algorithm X using DLX
  • Introduction to Grover's Algorithm
  • Art Gallery Problem
  • Preemptive Priority CPU Scheduling Algorithm
  • Transform and Conquer Technique
  • Representation Change in Transform and Conquer Technique
  • What Does Big O(N^2) Complexity Mean?
  • Algorithm definition and meaning
  • How to write a Pseudo Code?
  • How to develop an Algorithm from Scratch | Develop Algorithmic Thinking
  • Approximation Algorithms
  • Accounting Method | Amortized Analysis
  • Genetic Algorithms
  • Difference between average case and amortized analysis
  • Polynomial Time Approximation Scheme
  • Josephus Problem when k is 2
  • Minimum number of items to be delivered
  • How to store the data for multiple objectives in Shortest path search 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.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule. Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

  • DSA in Java
  • DSA in Python
  • DSA in JavaScript

Please Login to comment...

  • nikhilgarg527
  • kake_karthik
  • Flask Mega-Tutorial 2024: A Complete Update for Python Enthusiasts
  • Google Maps on Android: Now Featuring Current Weather Information
  • Apple's 2024 iPad Pro: Bigger OLED Screen, M3 Chip, and a Better Magic Keyboard
  • Microsoft to Train 2 Mn in AI by 2025: A Game-Changer for Employment and Skill Development
  • 30 OOPs Interview Questions and Answers (2024)

Improve your Coding Skills with Practice

geeksforgeeks-footer-logo

Optimization of fuzzy bi-objective fractional assignment problem

  • Application Article
  • Published: 13 March 2019
  • Volume 56 , pages 1091–1102, ( 2019 )

Cite this article

  • Neha Gupta 1  

229 Accesses

5 Citations

Explore all metrics

A Correction to this article was published on 03 June 2019

This article has been updated

Theory and applications of fractional programming have been significantly developed in the few last decades and assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization. Generally, in real world problems, the possible values of coefficients of a linear fractional programming problem are often only imprecisely or ambiguously known to the decision maker, therefore, it would be certainly more appropriate to interpret the coefficients as fuzzy numerical data. In this article, a fuzzy bi-objective fractional assignment problem has been formulated. Here the parameters are represented by triangular fuzzy numbers and the fuzzy problem is transformed into standard crisp problem through \(\alpha \) -cut and then the compromise solution is derived by fuzzy programming.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

quadratic assignment problem fuzzy

Change history

03 june 2019.

In the original published article the “Conclusion and future scope” paragraph has been incorrectly published.

Triangular Fuzzy number (TFN) A fuzzy number \({\tilde{A}}=(p,q,r)\) is said to be a triangular fuzzy number if its membership function is given by

Akkapeddi, S.M.: Fuzzy programming with quadratic membership functions for multi-objective transportation problem. Pak. J. Stat. Oper. Res. 11 (2), 231–240 (2015)

Article   Google Scholar  

Bellman, R.E., Zadeh, L.A.: Decision-making in a fuzzy environment. Manag. Sci. 17 (4), B-141 (1970)

Charnes, A., Cooper, W.W.: Programming with linear fractional functionals. Naval Res. Logist. Q. 9 (3–4), 181–186 (1962)

De, P.K., Yadav, B.: A general approach for solving assignment problems involving with fuzzy cost coefficients. Mod. Appl. Sci. 6 (3), 2 (2012)

Dinkelbach, W.: On nonlinear fractional programming. Manag. Sci. 13 , 492–498 (1967)

Gupta, R.: Decomposition method and transportation type problems with a fractional objective function. ZAMM-J. Appl. Math. Mech. (Zeitschrift fr Angewandte Mathematik und Mechanik) 57 (2), 81–88 (1977)

Kar, S., Basu, K., Mukherjee, S.: Solution of generalized fuzzy assignment problem with restriction on costs under fuzzy environment. Int. J. Fuzzy Math. Syst. 4 , 169–180 (2014)

Google Scholar  

Kumar, A., Gupta, A., Kaur, A.: Method for solving fully fuzzy assignment problems using triangular fuzzy numbers. World Acad. Sci. Eng. Technol. Int. J. Comput. Electr. Autom. Control Inf. Eng. 3 (7), 1889–1892 (2009)

Kumar, P.S., Hussain, R.J.: A method for solving balanced intuitionistic fuzzy assignment problem. Int. J. Eng. Res. Appl. 4 (3), 897–903 (2014)

Lin, C.J.: A simplex-based labelling algorithm for the linear fractional assignment problem. Optimization 64 (4), 929–939 (2015)

Lin, C.J., Wen, U.P.: A labeling algorithm for the fuzzy assignment problem. Fuzzy Sets Syst. 142 (3), 373–391 (2004)

Pandian, P., Kavitha, K.: A new method for solving fuzzy assignment problems. Ann. Pure Appl. Math. 1 , 69–83 (2012)

Sadia, S., Gupta, N., Ali, Q.M.: Multiobjective capacitated fractional transportation problem with mixed constraints. Math. Sci. Lett. 5 (3), 235–242 (2016)

Sakawa, M., Nishizaki, I., Uemura, Y.: Interactive fuzzy programming for two-level linear and linear fractional production and assignment problems: a case study. Eur. J. Oper. Res. 135 (1), 142–157 (2001)

Saruwatari, Y., Shigeno, M., Matsui, T.: An algorithm for fractional assignment problems. Discrete Appl. Math. 56 (2), 333–343 (1995)

Swarup, K.: Transportation technique in linear fractional functional programming. J. R. Naval Sci. Serv. 21 (5), 256–260 (1966)

Download references

Acknowledgements

The author express their sincere thanks to editor and referees for their valuable suggestions and comments, which improved the quality of the paper.

Author information

Authors and affiliations.

Faculty of Management Sciences, Amity University, Noida, India

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Neha Gupta .

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

Gupta, N. Optimization of fuzzy bi-objective fractional assignment problem. OPSEARCH 56 , 1091–1102 (2019). https://doi.org/10.1007/s12597-019-00367-2

Download citation

Accepted : 03 March 2019

Published : 13 March 2019

Issue Date : September 2019

DOI : https://doi.org/10.1007/s12597-019-00367-2

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

  • Assignment problem
  • Fractional programming problem
  • Fuzzy numbers
  • Fuzzy programming
  • Find a journal
  • Publish with us
  • Track your research

IMAGES

  1. (PDF) Multi-objective Fuzzy Quadratic Programming Problem using Taylor

    quadratic assignment problem fuzzy

  2. PPT

    quadratic assignment problem fuzzy

  3. On the Stability of Fuzzy Systems quadratic

    quadratic assignment problem fuzzy

  4. Solving Fuzzy Quadratic Programming Problems with a Proposed Algorithm

    quadratic assignment problem fuzzy

  5. PPT

    quadratic assignment problem fuzzy

  6. PPT

    quadratic assignment problem fuzzy

VIDEO

  1. My favorite quadratic solving method

  2. Programming Assignment II on MATLAB Fuzzy Logic

  3. assignment 1 Quadratic equation solver in C++

  4. Quadratic Formula Assignment Instructions

  5. Assignment No2 Fuzzy Logics MTH645

  6. Using the Quadratic Formula- Assignment

COMMENTS

  1. The fuzzy quadratic assignment problem with penalty: New models and

    1. Introduction The assignment problem (AP), which has been widely applied in both manufacturing and service systems, is to find the total costs optimal jobs assignment schedule where n jobs are allocated to n workers (or machines), and each worker receives exactly just one job. The AP is a special type of linear 0-1 programming.

  2. Quadratic assignment problem

    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.

  3. PDF The Quadratic Assignment Problem

    also considers problems related to the QAP, e.g. the biquadratic assignment problem, and discusses the relationship between the QAP and other well known combinatorial optimization problems, e.g. the traveling salesman problem, the graph partitioning problem, etc. The paper will appear in the Handbook of Combinatorial Optimization to be published

  4. A comprehensive review of quadratic assignment problem: variants

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

  5. Study on solution models and methods for the fuzzy assignment problems

    Based on fuzzy structural characteristics, we propose the concept of level effect function. It can be used to establish an IL -metric method to measure all aspects of fuzzy information. This algorithm in systems perspectives can be widely used in many assignment problems. Introduction

  6. A Fuzzy Particle Swarm Approach to Multiobjective Quadratic Assignment

    This paper introduces a fuzzy particle swarm algorithm to handle the Multiobjective Quadratic Assignment Problem (mQAP). In the fuzzy scheme, the representations of the position and velocity of the particles in the conventional PSO is extended from the real vectors to fuzzy matrices.

  7. The fuzzy quadratic assignment problem with penalty: New models and

    The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm @article{Liu2006TheFQ, title={The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm}, author={Linzhong Liu and Yinzhen Li}, journal={Appl. Math. Comput.}, year={2006}, volume={174}, pages={1229-1244}, url={https://api ...

  8. Li, Y.: The fuzzy quadratic assignment problem with ...

    The fuzzy quadratic assignment problem with penalty: New models and genetic algorithm. Applied Mathematics and Computation 174 (2), 1229-1244 DOI: Authors: Linzhong Liu Tsinghua...

  9. A Fuzzy Particle Swarm Approach to Multiobjective Quadratic Assignment

    A fuzzy particle swarm algorithm to handle the Multiobjective Quadratic Assignment Problem (mQAP) is introduced, in the fuzzy scheme, the representations of the position and velocity of the particles in the conventional PSO is extended from the real vectors to fuzzy matrices. The multiobjective Quadratic Assignment Problem (mQAP) is considered as one of the hardest optimization problems but ...

  10. A Fuzzy Particle Swarm Approach to Multiobjective Quadratic Assignment

    The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and ...

  11. A fuzzy particle swarm approach to multiobjective quadratic assignment

    In this paper a particle swarm optimization algorithm is presented to solve the Quadratic Assignment Problem, which is a NP-Complete problem and is one of the most interesting and challenging combinatorial optimization problems in existence.

  12. The fuzzy quadratic assignment problem with penalty: New models and

    In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models.

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

  14. Quadratic assignment problem

    The formal definition of the quadratic assignment problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, together with a weight function w : P × P → R and a distance function d : L × L → R. Find the bijection f : P → L ("assignment") such that the cost function: is minimized.

  15. An hybrid fuzzy variable neighborhood particle swarm optimization

    A fuzzy particle swarm approach to multiobjective quadratic assignment problems 2008 • Ajith Abraham Abstract The multiobjective Quadratic Assignment Problem (mQAP) is considered as one of the hardest optimization problems but with many real-world applications.

  16. Optimization of fuzzy bi-objective fractional assignment problem

    The fuzzy assignment problem (FAP) is more realistic than the assignment problem (AP) because most real environments are uncertain. Sakawa et al. [ 14 ] applies interactive fuzzy programming for two level linear and linear fractional assignment problem and derive satisfactory solution to the problem based on production and work force assignment ...

  17. An algorithm for Quadratic Assignment Problems

    In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models.

  18. A solution approach for a fully fuzzy assignment problem

    Abstract and Figures. We solve a fully fuzzy assignment problem (FAP) where the costs are triangular fuzzy numbers. The FAP has gained its importance in the recent years. We have represented the ...

  19. PDF Fuzzy Assignment Problem with Generalized Fuzzy Numbers

    the classical assignment problems are proposed e.g. bottleneck assignment problem, generalized assignment problem, quadratic assignment problem etc. In recent years, fuzzy transportation and fuzzy assignment problems have received much concentration. Lin and Wen [8] proposed an efficient algorithm based on

  20. A 'fuzzy' heuristic for the quadratic assignment formulation to the

    This paper describes a fuzzy set theory based heuristic for the quadratic assignment formulation of the facility layout problem with single/multiple objectives.

  21. On solutions of fuzzy random multiobjective quadratic programming with

    Liu and Li [21] studied the fuzzy quadratic assignment problem with penalty as expected value model, chance-constrained programming and dependent-chance programming. Tanaka and Ishibuchi [33] considered quadratic membership functions to propose an identification method of interactive fuzzy parameters in possibilistic linear systems. Tang and ...

  22. PDF Solving Fuzzy Assignment Problem Using Numerical Quadrature Formula

    The assignment problem (AP) is a special type of linear programming problem in which our objective is to assign various number of jobs to an equal number of persons at a minimum cost. All the algorithms developed to find the optimal solution of Transportation problem are applicable to assignment problem.

  23. The Quadratic Assignment Problem

    It is shown that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap, which has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix.

  24. A hybrid fuzzy logic based ant colony routing optimization ...

    Ant colony optimisation algorithms have been applied to a wide range of combinatorial optimisation problems, from quadratic assignment to protein folding or routing vehicles. ... Ant colony optimisation algorithm (HFACO) and hybrid fuzzy logic were used in the construction of the routing protocol. Numerous derived techniques have been adapted ...