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
Binary search tree. A binary search tree is a binary tree that is either empty or in which every node having a key that satisfies the following conditions: - All keys (if an

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

A binary search tree (BST), which may sometimes also be named a sorted or ordered binary tree, is an edge based binary tree data structure which has the following functionalities:

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

circular queue using c

Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

Explain an efficient and effective way of storing two symmetric matrices of the same order in the memory. A n-square matrix array will be symmetric if a[j][k]=a[k][j] for all j