Scribd Logo
Upload

Welcome to Scribd!

  • 128 views

    Quadratic Assignment Problem

    Uploaded by

    Pramod Kumar Verma
    The quadratic assignment problem (qap) is one of fundamental combinatorial optimization problems. The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. The formal definition of the problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, Find the bijection f : P - L ("assignment")

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd

    Quadratic Assignment Problem

    Uploaded by

    Pramod Kumar Verma
    128 views3 pages
    The quadratic assignment problem (qap) is one of fundamental combinatorial optimization problems. The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. The formal definition of the problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, Find the bijection f : P - L ("assignment")

    Original Title

    Quadratic assignment problem

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The quadratic assignment problem (qap) is one of fundamental combinatorial optimization problems. The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. The formal definition of the problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, Find the bijection f : P - L ("assignment")

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    128 views3 pages

    Quadratic Assignment Problem

    Uploaded by

    Pramod Kumar Verma
    The quadratic assignment problem (qap) is one of fundamental combinatorial optimization problems. The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. The formal definition of the problem is as follows: Given two sets, P ("facilities") and L ("locations"), of equal size, Find the bijection f : P - L ("assignment")

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    Quadratic assignment problem

    From Wikipedia, the free encyclopedia


    Jump to: navigation, search
    The quadratic assignment problem (QAP) is one of fundamental combinatorial
    optimization problems in the branch of optimization or operations research in mathematics,
    from the category of the facilities location problems.
    The problem models the following real-life problem:
    There are a set of n facilities and a set of n locations. For each pair of locations, a
    distance is specified and for each pair of facilities a weight or flow is specified (e.g.,
    the amount of supplies transported between the two facilities). The problem is to
    assign all facilities to different locations with the goal of minimizing the sum of the
    distances multiplied by the corresponding flows.
    The problem statement resembles that of the assignment problem, only the cost function is
    expressed in terms of quadratic inequalities, hence the name.

    Contents
    [hide]
    • 1 Formal mathematical definition
    • 2 Computational complexity
    • 3 Applications
    • 4 See also
    • 5 References

    [edit] Formal mathematical definition


    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.
    Usually weight and distance functions are viewed as square real-valued matrices, so that the
    cost function is written down as:

    [edit] Computational complexity


    The problem is NP-hard, so there is no known algorithm for solving this problem in
    polynomial time, and even small instances may require long computation time. The
    Travelling salesman problem may be seen as a special case of QAP if one assumes that the
    flows connect all facilities only along a single ring, all flows have the same non-zero
    (constant) value. Many other problems of standard combinatorial optimization problems may
    be written in this form.
    [edit] Applications
    In addition to the original plant location formulation, QAP is a mathematical model for the
    problem of placement of interconnected electronic components onto a printed circuit board or
    on a microchip, which is part of the place and route stage of computer aided design in the
    electronics industry.
    [edit] See also
    • Quadratic bottleneck assignment problem
    [edit] References
    • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A
    Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.
    A2.5: ND43, pg.218.
    Retrieved from "http://en.wikipedia.org/wiki/Quadratic_assignment_problem"
    Categories: NP-hard problems | Combinatorial optimization
    Personal tools
    • Log in / create account
    Namespaces
    • Article
    • Discussion
    Variants
    Views
    • Read
    • Edit
    • View history
    Actions
    Search
    Top of Form
    Special:Search

    Search

    Bottom of Form
    Navigation
    • Main page
    • Contents
    • Featured content
    • Current events
    • Random article
    • Donate to Wikipedia
    Interaction
    • Help
    • About Wikipedia
    • Community portal
    • Recent changes
    • Contact Wikipedia
    Toolbox
    • What links here
    • Related changes
    • Upload file
    • Special pages
    • Permanent link
    • Cite this page
    Print/export
    • Create a book
    • Download as PDF
    • Printable version
    Languages
    • Español
    • This page was last modified on 22 November 2010 at 20:28.
    • Text is available under the Creative Commons Attribution-ShareAlike License;
    additional terms may apply. See Terms of Use for details.
    Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit
    organization.
    • Contact us
    • Privacy policy
    • About Wikipedia
    • Disclaimers

    You might also like