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
Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w

Q. Define a sparse matrix. Explain different types of sparse matrices? Show how a triangular array is stored in memory. Evaluate the method to calculate address of any element ajk

Q. Explain the various memory allocation strategies.                                                            Ans. M e m ory Allocation Strategies are given as follow

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

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

Technique for direct search is    Hashing is the used for direct search.

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write


what happen''s in my computer when i input any passage