Branch and bound algorithm, Data Structure & Algorithms

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out an assignment which results in the least total cost. Your task is to write a c++ program to implement the branch and bound algorithm to solve this assignment problem.

Your program should read input data from a input file named "infile.txt". The format for the input file is as follows: First line is an integer N representing the number of agents and the number of jobs. In the next N lines, each line j (1 ≤ j ≤ N) consists of N integers representing the cost of assigning agent j to each of the N tasks.

Figure 1 gives you an example of the input format. For example, the cost of assigning agent 1 to task 1, 2, 3 and 4 are 11, 12, 18 and 40 respectively.

4

11 12 18 40

14 15 13 22

11 17 19 23

17 14 20 28

Figure 1

Total cost: 61
(1,1)
(2,3)
(3,4)
 (4,2)

Figure 2

Output, to standard output, will consist of:

  • Total cost of the assignment
  • In the next N lines, each line j (1 ≤ j ≤ N) shows the task assignment for agent j in the format "(j,k)", which means agent j is assigned to task k.

Figure 2 gives you an example of the output screen for the input file in Figure 1.

Posted Date: 2/25/2013 6:56:11 AM | Location : United States







Related Discussions:- Branch and bound algorithm, Assignment Help, Ask Question on Branch and bound algorithm, Get Answer, Expert's Help, Branch and bound algorithm Discussions

Write discussion on Branch and bound algorithm
Your posts are moderated
Related Questions
Count Scorecards(30 points) In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a

Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

what is an algorithms

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

Write a recursive function the computes the number of digits in a positive integer n. For example if n = 6598, the function should return 4. Find a variant expression and a thresho

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

what is far and near procedures in system programming?

infix to revrse polish

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic