Branch and bound algorithm, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Branch and bound algorithm

Queue, algorithm for insertion in a queue using pointers

algorithm for insertion in a queue using pointers

Insertion of element into a linked list, ALGORITHM (Insertion of element in...

ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

How does an array differ from an ordinary variable, Normal 0 fa...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ...

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Creation of doubly linked list, Program: Creation of Doubly Linked List ...

Program: Creation of Doubly Linked List OUTPUT Input the values of the element -1111 to come out : 1 Input the values of the element -1111 to come out : 2 Inpu

Define approximating smooth surfaces with polygon nets, Approximating smoot...

Approximating smooth surfaces with Polygon nets Networks of polygons are used to represent smooth surfaces. They are, of course, only an approximation to the true surface, but

B-tree of minimum degree t can maximum pointers in a node, A B-tree of mini...

A B-tree of minimum degree t can maximum pointers in a node T pointers in a node.

Algorithm, what algorithms can i use for the above title in my project desi...

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

Search engines - applications of linear and binary search, Search engines e...

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd