In: Computer Science
to be written in c++ only
Objectives
To be able to solve problem using branch an bound strategy
To be able to find the minimized cost
To practice writing solutions to problems in a clear and succinct
way
Problem
Let there be N workers and N jobs. Any worker can be assigned to
perform any job, incurring
some cost that may vary depending on the work-job assignment. It is
required to perform all jobs
by assigning exactly one worker to each job and exactly one job to
each agent in such a way that
the total cost of the assignment is minimized. Write a program
using branch and bound strategy to
show who will be assigned which job and the total cost
incurred.
Given Problem: There are N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.
Branch & Bound method: Branch and bound is an
algorithm design paradigm which is generally used for solving
combinatorial optimization problems. These problems are typically
exponential in terms of time complexity and may require exploring
all possible permutations in worst case. The Branch and Bound
Algorithm technique solves these problems relatively quickly.
Let us consider there are 5 jobs numbered as {0,1,2,3,4} & 5 worker named as {A,B,C,D,E};
/*
* job assignment problem
* N- jobs & N- worker, find out the minimum total cost
incurred.
* written by: Sanket
* Date: 30/10/2019
*/
#include <bits/stdc++.h>
using namespace std;
#define N 5 // In this example we are considering 5worker and 5
jobs
//we can change this no. as per no. of workers
// state space tree node
struct Node
{
// stores parent node of current node
// helps in tracing path when answer is found
Node* parent;
// contains cost for ancestors nodes
// including current node
int pathCost;
// contains least promising cost
int cost;
// contain worker number
int workerID;
// contains Job ID
int jobID;
// Boolean array assigned will contains
// info about available jobs
bool assigned[N];
};
// Function to allocate a new search tree node
// Here Person x is assigned to job y
Node* newNode(int x, int y, bool assigned[], Node* parent)
{
Node* node = new Node;
for (int j = 0; j < N; j++)
node->assigned[j] =
assigned[j];
node->assigned[y] = true;
node->parent = parent;
node->workerID = x;
node->jobID = y;
return node;
}
// Function to calculate the least promising cost
// of node after worker x is assigned to job y.
int calculateCost(int costMatrix[N][N], int x, int y, bool
assigned[])
{
int cost = 0;
// to store unavailable jobs
bool available[N] = {true};
// start from next worker
for (int i = x + 1; i < N; i++)
{
int min = INT_MAX, minIndex =
-1;
// do for each job
for (int j = 0; j < N;
j++)
{
// if job is
unassigned
if (!assigned[j]
&& available[j] && costMatrix[i][j] < min)
{
// store job number
minIndex = j;
// store cost
min = costMatrix[i][j];
}
}
// add cost of next worker
cost += min;
// job becomes unavailable
available[minIndex] = false;
}
return cost;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* lhs, const Node* rhs)
const
{
return lhs->cost >
rhs->cost;
}
};
// print who is assigned to which job
void printAssignments(Node *min)
{
if(min->parent==NULL)
return;
printAssignments(min->parent);
cout <<"Worker" << char(min->workerID +
'A') << " assigned"<< " to Job " << min->jobID
<< endl;
}
// Finds minimum cost using Branch and Bound.
int findMinCost(int costMatrix[N][N])
{
// Create a priority queue to store live nodes of
search tree;
priority_queue<Node*, std::vector<Node*>,
comp> pq;
// initailize heap to dummy node with cost 0
bool assigned[N] = {false};
Node* root = newNode(-1, -1, assigned, NULL);
root->pathCost = root->cost = 0;
root->workerID = -1;
// Add dummy node to list of live nodes;
pq.push(root);
// Finds a live node with least cost,
// add its childrens to list of live nodes and
// finally deletes it from the list.
while (!pq.empty())
{
// Find a live node with least estimated cost
Node* min = pq.top();
// The found node is deleted from the list of
// live nodes
pq.pop();
// i stores next worker
int i = min->workerID + 1;
// if all workers are assigned a job
if (i == N)
{
printAssignments(min);
return min->cost;
}
// do for each job
for (int j = 0; j < N; j++)
{
// If unassigned
if (!min->assigned[j])
{
// create a new tree node
Node* child = newNode(i, j,
min->assigned, min);
// cost for ancestors nodes
including current node
child->pathCost =
min->pathCost + costMatrix[i][j];
// calculate its lower
bound
child->cost = child->pathCost
+ calculateCost(costMatrix, i, j, child->assigned);
// Add child to list of live
nodes;
pq.push(child);
}
}
}
}
// Driver code
int main()
{
// x-cordinate represents a Worker & y-cordinate
represents a Job
// Matrix is 5*5 because in this example we are considering 5 worker & 5 jobs.
// // you can also take costMatrix values from user
int costMatrix[N][N] =
{
{9, 2, 7, 8,8},
{6, 4, 3, 7,17},
{5, 8, 1, 8,5},
{7, 6, 9, 4,10},
{12,9,3,10,13}
};
cout << "\nThe total cost incurred "<<
findMinCost(costMatrix);
return 0;
}