Welcome to MSDN Blogs Sign in | Join | Help

Browse by Tags

All Tags » QAP » C#   (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

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
 
Page view tracker