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
By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

A Stack has an ordered list of elements & an array is also utilized to store ordered list of elements. Therefore, it would be very simple to manage a stack by using an array. Thoug

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

An adjacency matrix representation of a graph cannot having information of : Parallel edges

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Sort the following array of elements using quick sort: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8.

algorithm for insertion in a queue using pointers