Answer Happy

Q3 Auction Algorithm (5 marks) Implement the auction algorithm for solving assignment problems as discussed in the. To make the costs integer as required by this algorithm use costs Cij = Pis +(507 Vie C, JER where [x] is the largest integer < x (as given by the floor() function) Test that this produces exactly the same solution as the LP based solution method and report 1. The optimal objective value 2. The final solution (assignment vector a) 3. The optimal vector of prices (penalties) for each room. 4. The runtime of your method in seconds) 5. A graph of runtime against problem size. This should give an indication of how the algorithm scales with increasing problem size. You should generate random integer cost matrices C e Znxn for this. The choice of different n values is up to you but the с expectation is that you can get a reasonable graph with a few different values of n such that the run time on any instance is no more than about one minute.