You are given the following data for a knapsack problem with 8 items. The objective is...

Transcribed Image Text:

You are given the following data for a knapsack problem with 8 items. The objective is to maximize value without exceeding the knapsack size of 50. ITEM 2 3 4 30 26 SIZE 21 11 51 13 32 VALUE 37 12 50 500 41 13 10 45 For this problem, write your answers to the questions. You do not need to submit an excel file. a) Write the mathematical integer programming model of the problem. b) Solve the LP relaxation of the problem in Excel with Solver. What is the solution? c) Based on the solution from (b), what is a cut that eliminates the non-integer solution to the LP relaxation, but does not eliminate any solutions to the integer problem? d) Add the cut to the LP and solve the LP again. What is the solution? e) Based on the solution from (d), what is a cut that eliminates the non-integer solution to the LP relaxation solution in (d), but does not eliminate any solutions to the integer problem? f) Add this second cut to the LP relaxation (you should know have both cuts in the problem) and solve it. What is the solution? 8) What is the next cut? h) Now solve the IP with the three additional cuts. What is the solution? i) What is the difference between the optimal solution (z-value) and the best bound you found (z- value at step f)? Notice that this is a much tighter bound than the initial LP relaxation. You are given the following data for a knapsack problem with 8 items. The objective is to maximize value without exceeding the knapsack size of 50. ITEM 2 3 4 30 26 SIZE 21 11 51 13 32 VALUE 37 12 50 500 41 13 10 45 For this problem, write your answers to the questions. You do not need to submit an excel file. a) Write the mathematical integer programming model of the problem. b) Solve the LP relaxation of the problem in Excel with Solver. What is the solution? c) Based on the solution from (b), what is a cut that eliminates the non-integer solution to the LP relaxation, but does not eliminate any solutions to the integer problem? d) Add the cut to the LP and solve the LP again. What is the solution? e) Based on the solution from (d), what is a cut that eliminates the non-integer solution to the LP relaxation solution in (d), but does not eliminate any solutions to the integer problem? f) Add this second cut to the LP relaxation (you should know have both cuts in the problem) and solve it. What is the solution? 8) What is the next cut? h) Now solve the IP with the three additional cuts. What is the solution? i) What is the difference between the optimal solution (z-value) and the best bound you found (z- value at step f)? Notice that this is a much tighter bound than the initial LP relaxation.

Answer rating: 100% (QA)

a The mathematical integer programming model of the problem is given by Maximize Z 21x1 37x2 1x3 11x... View the full answer