Compartilhar via

Quadratic Assignment Problems, Part I

  • Artigo

Thanks for visiting! I have moved my blog. An updated version of this post can be found here.

Comments

  • Anonymous
    April 28, 2008
    PingBack from http://microsoftnews.askpcdoc.com/qap/quadratic-assignment-problems-part-i

  • Anonymous
    May 03, 2008
    In my last post I introduced quadratic assignment problems. Branch-and-bound algorithms are the most

  • Anonymous
    December 06, 2008
    Can i know what the input information from user for solving quadratic assignment problem in programming? Beside number of facilities and location, do we still need other information?

  • Anonymous
    December 06, 2008
    Donald, that is a good question, and answering it fully probably requires a separate blog posting.  The short answer is that three pieces of information are required:

  1. The number of facilities / locations
  2. The distance between each pair of locations
  3. The "flow" or "amount of materials" between each pair of facilities It is often convenient to represent 2) and 3) as graphs or matrices.  In my lab example above, it's pretty easy to determine 2 and 3 - for example I might just walk between rooms and use the stopwatch time for the distance.  For flows I could take measurements for a day to determine how often people walk from one part of the lab to the other. The distances are often "symmetric": the distance from A to B is the same as the distance from B to A.  But that isn't always the case - for example, driving from Everett to Seattle at 9:00 AM might take much longer than from Seattle to Everett because of traffic. There are other applications for QAP where it's more difficult to determine the flows and distances.  Translating a real world description of a problem into an optimization problem is called "modeling" and is an interesting area all to itself.  Microsoft Solver Foundation is a huge help in modeling problems like these.