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.


11 12 18 40

14 15 13 22

11 17 19 23

17 14 20 28

Figure 1

Total cost: 61

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
Write the algorithm for compound interest

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

A connected graph is a graph wherein path exists among every pair of vertices. A strongly connected graph is a directed graph wherein every pair of distinct vertices is connecte

Q. What do you understand by the term Binary Tree? What is the maximum number of nodes which are possible in a Binary Tree of depth d. Explain the terms given below with respect to

Q. Let X = (X1, X2, X3,....Xn) and Y= (Y1, Y2, Y3,....Xm) be the two linked lists respectively. Write down an algorithm to merge the lists together to get the linked list Z such th

Q.   Draw the expression tree of the infix expression written below and then  convert it intoPrefix and Postfix expressions. ((a + b) + c * (d + e) + f )* (g + h )

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

explain quick sort algorithm

Explain an efficient method of storing a sparse matrix in memory. Write a module to find the transpose of the sparse matrix stored in this way. A matrix which contains number o