Question

In: Computer Science

to be written in c++ only Objectives  To be able to solve problem using branch...

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.

Solutions

Expert Solution

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;
}


Related Solutions

Objectives: Practice using selection structures within a complete C++ program to solve a problem. Be able...
Objectives: Practice using selection structures within a complete C++ program to solve a problem. Be able to understand and use linear interpolation in a program. Modify/Extend an existing program. Problem Description: Linear Interpolation There are two credit levels for this assignment. Completing the “B” level correctly is worth 16/20 points, completing the “A” level is worth 20/20. You are encouraged to get the code for the “B” level working first and then complete the “A” level if you have time/interest....
solve following travelling salesman problem using branch and bound and show matrix and graph at each...
solve following travelling salesman problem using branch and bound and show matrix and graph at each step 5 locations : a, b, c, d, e from a to remaining places = [infinity, 4, 7, 3, 4] from b to remaining places = [4, infinity, 6, 3, 4] from c to remaining = [7, 6, infinity, 7, 5] from d to remaining = [3, 3, 7, infinty, 7] from e to remaining = [4, 4, 5, 7, infinity] PLEASE show ALL...
Longest ‘A’ Path Objectives Manipulating two-dimensional lists Using recursion to solve a problem Problem Specification Write...
Longest ‘A’ Path Objectives Manipulating two-dimensional lists Using recursion to solve a problem Problem Specification Write a Python application to find the longest ‘A’ path on a map of capital (uppercase) letters. The map is represented as a matrix (2-dimensional list) of capital letters. Starting from any point, you can go left, right, up and down (but not diagonally). A path is defined as the unbroken sequence of letters that only covers the spots with the letter A. The length...
The code should be written in c++. It should be in only OpenGL // ***** ONLY...
The code should be written in c++. It should be in only OpenGL // ***** ONLY OpenGL PLEASE ******// write a program snippet that accepts the coordinates of the vertices of a rectangle centered around the origin, with edges that are parallel to the X and Y axes, and with aspect ratio W and converts it into a rectangle centered around the origin with aspect ratio of 1/W. The program has to figure W from the given points. You MUST...
c# only please Objectives Use the more advanced data structures introduced to accomplish a difficult problem....
c# only please Objectives Use the more advanced data structures introduced to accomplish a difficult problem. Tasks This assignment has two parts: Read from a file. Write to a file. Task 1 – File Input The first piece of information we need is a text file’s name and location. Ask the user through the console what the file’s name and location are. After that, please ensure that the file does exist and at the given location. If the file does...
Objectives: Learn to analyze a computational problem and construct an algorithm to solve it Learn to...
Objectives: Learn to analyze a computational problem and construct an algorithm to solve it Learn to use sequential statements to build a basic program to implement the algorithm, using correct programming format Learn to use the scanf function to read and store values entered on the keyboard by the user, and the printf function used to display output results on the computer monitor Learn to convert math formulas into correct arithmetic expressions using variables, constants, and library math functions Learn...
Please outline each step used along the way to solve the problem using excel only with...
Please outline each step used along the way to solve the problem using excel only with cell numbers and formulas used. Thank you. Whenever an Alliance Air customer flies on a prepurchased seat, Alliance Air obtains $100 in profits. However, if Alliance Air has more customers seeking a seat then they have prepurchased, Alliance Air is forced to book that passenger on a seat purchased that day. In such a situation, Alliance Air has a profit of -$170 due to...
We have to solve only problem 2, I'm sharing Problem 1 only for reference purpose. Problem...
We have to solve only problem 2, I'm sharing Problem 1 only for reference purpose. Problem 1. (25 points) Alice is going to create a notebook including the profile of all her friends. For each of her friends, she would like to keep first-name, last-name, cell number, and birthdate (month and day). At the beginning, she doesn’t know how many spaces she should reserve for recording her friends, so she gradually inputs her friends’ information into it. • Please help...
Objectives: use Scite Use recursion to solve a problem Create classes to model objects Problem :...
Objectives: use Scite Use recursion to solve a problem Create classes to model objects Problem : The Rectangle class (Filename: TestRectangle.java) Design a class named Rectangle to represent a rectangle. The class contains: Two double data fields named width and height that specify the width and height of the rectangle. The default values are 1 for both width and height. A no-arg constructor that creates a default rectangle. A constructor that creates a rectangle with the specified width and height....
You are required to use only C for this problem. To begin, instead of using two...
You are required to use only C for this problem. To begin, instead of using two different variables for this problem, you are going to define a structure with two members; one representing the feet and the other one representing the inches. We will also use three functions; one to initialize a structure, one to check the validity of its values, and the last one to print them out. First, define your structure. Next, declare a structure of this type...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT