Assignment Problem Algorithm C#

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:

Code:

#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); } }
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.

Copyright (c) 2009, Yi Cao
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

* Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in
the documentation and/or other materials provided with the distribution

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

Comments

Leave a Reply

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