Welcome to MSDN Blogs Sign in | Join | Help

Browse by Tags

All Tags » QAP   (RSS)

Quadratic Assignment Problems: solution enumeration

Posted Monday, July 27, 2009 9:53 AM by Nathan Brixius
In the last few posts we have given code for computing the Gilmore Lawler bound for quadratic assignment problems, and described two different branching techniques . In this post we show how to enumerate solutions of a small QAP. The possible solutions Read More...
0 Comments

Quadratic Assignment Problems: strong and weak branching

Posted Sunday, July 19, 2009 7:19 PM by Nathan Brixius
Let's pick up where we left off last time and write a score-based Branch delegate. It will be used as the basis for both of our "real" branching functions. private BranchingDecision BranchCore( BranchAndBoundNode node, double bound, double [][] S) { RowColumnSums(S, Read More...
0 Comments

Quadratic assignment problems: branching

Posted Sunday, July 12, 2009 4:24 PM by Nathan Brixius
(This is part of a long-running series on quadratic assignment problems in C#. Click here to catch up. ) Branching means to divide the search space represented by a node into subnodes. QAP is about making assignments of facilities to locations, so two Read More...
0 Comments

Simple matrix, vector, permutation utilities

Posted Tuesday, March 24, 2009 9:24 PM by Nathan Brixius
I am going to be rolling out the rest of my branch-and-bound algorithm in the next few posts. To make that easier, in this post I introduce some common matrix, vector, and permutation methods. It turns out that for technical computing applications, C#'s Read More...
1 Comments

Branch-and-bound algorithms for QAP

Posted Monday, March 23, 2009 1:22 PM by Nathan Brixius
This is part 4 in a series of posts laying out a simple branch-and-bound solver for QAP in C#. Last time (several months ago!) I provided a simple bounding procedure for QAP. I want to take a step back and give the high-level algorithm, then in subsequent Read More...
3 Comments

Announcing Microsoft Solver Foundation

Posted Friday, November 14, 2008 10:26 AM by Nathan Brixius
I'm pleased to announce the availability of the first version of Microsoft Solver Foundation ! Simply put, Solver Foundation is a set of modeling tools and solvers to help you make smart decisions when confronted with complex requirements and priorities. Read More...
3 Comments

Quadratic assignment problems: bounds

Posted Thursday, July 10, 2008 12:34 PM by Nathan Brixius
This is part 3 of what will be a long series about how to solve QAPs using branch-and-bound. My goal to end up with a simple branch-and-bound algorithm in C#. In my last post I wrote down the formulation for QAP, wrote a QAP class in C#, and showed how Read More...
4 Comments
Filed under:

Quadratic Assignment Problems: branch and bound

Posted Saturday, May 03, 2008 11:16 AM by Nathan Brixius
In my last post I introduced quadratic assignment problems. As I explained, the problem is to assign an equal number of facilities to locations, minimizing the transportation cost. A compact way to write the problem is to store the "flows" in a matrix Read More...
3 Comments
Filed under:

Quadratic Assignment Problems, Part I

Posted Monday, April 28, 2008 7:25 PM by Nathan Brixius
In a previous series I talked a bit about linear assignment problems (LAPs) and provided code for a simple LAP solver. Now I want to spend a few posts on LAP's big brother, the Quadratic Assignment Problem. In an LAP we are trying to assign objects in Read More...
4 Comments
Filed under:

Linear assignment problems, part III

Posted Thursday, August 09, 2007 10:14 AM by Nathan Brixius
Here's the code. See the previous posting for background. using System; namespace NathanBrixius.AssignmentLib { /// <summary>Linear assignment problem solver.<summary> /// <remarks> /// This code is a port of Fortran code by R.E. Burkard Read More...
2 Comments

Linear assignment problems, part II

Posted Thursday, August 09, 2007 10:06 AM by Nathan Brixius
In a previous post I talked a bit about the linear assignment problem: finding the minimum cost matching in a bipartite graph. In my next post I will give a simple self-contained C# program for solving LAP based on some Fortran code from my colleague Read More...
2 Comments

Linear assignment problems, part I

Posted Monday, July 02, 2007 1:38 PM by Nathan Brixius
I'm going to devote a few posts to my thesis topic, the quadratic assignment problem . Quadratic assignment problems are a type of matching problem that are NP hard and have some interesting applications. I'll start out by describing linear assignment Read More...
2 Comments
 
Page view tracker