Branch and Bound Algorithm for solving Assignment-problem

[whyunomad]

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: http://statistics-assignment.com/wp-content/uploads/2012/10/1285.png

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 (!colUsed.at(col))
        {
            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 (colUsed.at(col++)); 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);

        colUsed.at(index) = true;
        assignedJobs.push_back(index);
    }
}

My matrix is 2D vector, and setmatrix() and print() functions are just for filling and printing the matrix.

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.

[gunnerfunner]

This could be a meaty problem but the information provided is not sufficient. If you want you can post the full problem and your code thus far somewhere and send the link through

[whyunomad]

Sure gunnerfunner i can put the code in cpp.sh if that's what you meant ?
The problem is that i'm getting completely wrong results so i must have programed the branch and bound wrong her.

[gunnerfunner]

Sure, please do that and also the full description of the problem