Branch And Bound Method For Assignment Problem Matrix

January 21st, 2017, 10:35 AM#1

Job assignment problem solve with Branch and Bound algorithm

I started doing Branch and Bound Algorithm for assignment problem in C++ and i can't find the right solution. First of all assignment problem example:

Ok so each person can be assigned to one job, and the idea is to assign each job to one of the person so that all the jobs are done in the quickest way.

Here is my code so far:


#include "Matrix.h" // Program to solve Job Assignment problem // using Branch and Bound #include <limits.h> #include <vector> #include <algorithm> using namespace std; template<class T> NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed); void run(Matrix& matrix, vector<size_t>& assignedJobs); int main() { Matrix matrix; matrix.setMatrix(N); matrix.print(); vector<size_t> assignedJobs; run(matrix, assignedJobs); cout << assignedJobs[0]; /* cout << "size:E " << v.size() << endl; for (vector<NUM>::iterator i = v.begin(); i != v.end(); i++) { cout << *i << endl; } */ return 0; } // remember to use x only LOCALLY!!! NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed) { // pathCost NUM pathCost = matrix.matrix[x++][y]; for (size_t col = 0; col < matrix.size(); col++) { if (! { NUM min = #if defined NUM_INT INT_MAX; #endif #if defined NUM_DBL DBL_MAX; #endif size_t row = x; for (; row < matrix.size(); row++) { if (min > matrix.matrix[row][col]) { min = matrix.matrix[row][col]; } } pathCost += min; } } return pathCost; } void run(Matrix& matrix, vector<size_t>& assignedJobs) { // array of used columns vector<bool> colUsed; for (size_t i = 0; i < matrix.size(); i++) { colUsed.push_back(false); } for (size_t row = 0; row < matrix.size(); row++) { size_t col = 0; // bombona while (; col--; // choose the best job for the current worker vector<NUM> jobs; // get all the job costs from which to choose the smallest // row++ jobs.push_back(getCost(matrix, col, row, colUsed)); // iterator at the position of the smallest element of jobs vector<NUM>::iterator i_min = min_element(jobs.begin(), jobs.end()); // index of the smallest element in jobs size_t index = (size_t)distance(jobs.begin(), i_min); = true; assignedJobs.push_back(index); } }
I know i might be out of track. I didn't use lower bound in the beginning, i'm actually a little confused how this algorithm exactly works. So even step by step walktrough through the algorithm would be helpful.

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 A, the “distances” in matrix B, and represent assignments as permutation matrices.  If you throw in a linear term C, then the problem can be written as:

Branch-and-bound algorithms are the most common technique for finding optimal solutions for QAP.  The next few posts will focus on describing how branch-and-bound works and will result in a complete implementation of a QAP solver in C#.  Branch-and-bound is a “divide and conquer” solution technique for combinatorial problems. Branch-and-bound repeatedly divides a problem into simpler subproblems of the same type, which are then solved or further subdivided. The search space of a problem is partitioned into search spaces for its subproblems. The algorithm generates a search tree with the root corresponding to the original problem to be solved.  At each node in the search tree, a relaxed version of the subproblem is solved, typically by loosening the constraints of the subproblem. The solution to the relaxation is a lower bound to the original subproblem. If a lower bound at a given node exceeds the value of a previously known solution, then continued searching on this path cannot lead to an improved solution, and there’s no need to continue searching on that node’s subtree (this is called “fathoming”).

A little less formally, we take the search space and divide it into subregions.  Then for each piece, we solve a “relaxed” version of the problem to see if we can rule out the solution lying in that subregion.  If we can’t rule it out, we divide the subregion into pieces and repeat.  The “relaxation” part is bounding, the dividing is called branching.  The effectiveness of a branch-and-bound algorithm depends on 1) the strength of the bound, 2) how fast bounds can be computed, and 3) the branching decisions.  For example, if the bound is terrible we’ll never fathom subproblems and we’ll end up searching the entire tree.

So how do we apply branch-and-bound to QAP?  The solution to a QAP is an assignment of facilities to locations.  Therefore the subproblems are obtained by assigning some of the facilities to locations.  To branch, I can pick a facility and try assigning it to each of the available locations (or vice-versa).  As we will see, the logic for selecting which facility/location to branch on is extremely important.

Let’s start putting together some of the pieces of our branch-and-bound solver for QAP.  First, let’s define a QAP, which as I said before consists of the flow and distance matrices A and B, and a linear term C.

// A quadratic assignment problem.publicclass Qap { // A (flow matrix).publicdouble[][] A { get; set; } // B (distance matrix).publicdouble[][] B { get; set; } // C (linear costs).publicdouble[][] C { get; set; } // Constant term.publicdouble Shift { get; set; } // Size of (A, B, C) matrices.publicint Size { get { return A == null ? 0 : A.Length; } } // Compute tr AXBX' + CX', where the permutation matrix X is determined by p.publicdouble Evaluate(int[] p) { double obj = this.Shift; for (int i = 0; i < A.Length; i++) { obj += this.C[i][p[i]]; for (int j = 0; j < A[i].Length; j++) { obj += this.A[i][j] * this.B[p[i]][p[j]]; } } return obj; } }

To make the code shorter I am using C# 3.0 automatic properties. In addition to the matrices I have also added a constant term “Shift”, whose purpose will become clear in a moment.  I’ve also provided a method called Evaluate() that computes the objective given a permutation.  Let’s think about how branching works.  If we go back to the mathematical formulation of QAP at the start of this post, assigning a facility to a location means setting X_ij = 1.  If we plug X_ij into the formula above we see that we end up with a QAP of size n – 1 with:

A′ = A(ii)
B′ = B(jj)
C′ = C(ij) + 2 a_i b_j ,
Shift’ = A[i][i] B[j][j] + C[i][j] + Shift

Where  A(ij) denotes matrix A with row i and column j removed, a_i are the elements in row i of A, excluding A[i][i], and let b_j are the elements in column j of B, excluding b[j][j]. Here’s the code:

privatestatic Qap Reduce(Qap qap, int i, int j) { Qap r = new Qap(); r.A = Reduce(qap.A, i, i); r.B = Reduce(qap.B, j, j); r.C = Reduce(qap.C, i, j); // Tack on: 2 a'_i b'_j (where a'_i is row i of A, with element i removed)for (int ii = 0; ii < r.Size; ii++) { for (int jj = 0; jj < r.Size; jj++) { r.C[ii][jj] += 2 * qap.A[i][ii < i ? ii : ii + 1] * qap.B[jj < j ? jj : jj + 1][j]; } } r.Shift = qap.Shift + qap.A[i][i] * qap.B[j][j] + qap.C[i][j]; return r; } privatestaticdouble[][] Reduce(double[][] M, int i, int j) { double[][] R = LinearAlgebra.NewMatrix(M.Length - 1); for (int ii = 0; ii < R.Length; ii++) { for (int jj = 0; jj < R[ii].Length; jj++) { R[ii][jj] = M[ii < i ? ii : ii + 1][jj < j ? jj : jj + 1]; } } return R; }

LinearAlgebra.NewMatrix() is a helper function that initializes the matrix. So now we have a data structure for QAP, and we now how to obtain subproblems.  Next time we’ll look at how to compute lower bounds.

Update 6/9/2010: Here is an additional method to read a problem in QAPLIB format.  It does not attempt to read the “C” matrix, and it is not totally robust. But it should work.

publicstatic Qap Read(StreamReader reader) { string content = reader.ReadToEnd(); var tokens = content.Split(newchar[] { ' ', '\n', '\r'}, StringSplitOptions.RemoveEmptyEntries); int k = 0; int size; if (Int32.TryParse(tokens[k++], NumberStyles.Integer, NumberFormatInfo.InvariantInfo, out size)) { Qap qap = new Qap(); qap.A = ReadMatrix(size, size, tokens, ref k); qap.B = ReadMatrix(size, size, tokens, ref k); return qap; } thrownew InvalidDataException("Invalid QAP size."); } privatestaticdouble[][] ReadMatrix(int m, int n, string[] tokens, refint k) { if (k + m * n > tokens.Length) { thrownew InvalidDataException("Not enough matrix data."); } double[][] matrix = LinearAlgebra.NewMatrix(m, n); for (int i = 0; i < matrix.Length; i++) { for (int j = 0; j < matrix[i].Length; j++) { if (!Double.TryParse(tokens[k++], NumberStyles.Float, NumberFormatInfo.InvariantInfo, out matrix[i][j])) { thrownew InvalidDataException("Invalid matrix entry."); } } } return matrix; }

Like this:



One thought on “Branch And Bound Method For Assignment Problem Matrix

Leave a Reply

Your email address will not be published. Required fields are marked *