Solve the following two problems with both exhaustive enumeration and branch and bound

   The assignment is worth 20 marks in total (20% of your final mark for the subject)

   Exhaustive enumeration is worth 4 marks for each problem, branch and bound is worth 5.5 marks for each problem, there is also 0.5 mark for self-assessment for  each problem.

   Problem 1 is a mixed integer linear optimisation problem (the problem has both

discrete and continuous variables). Do not use intlinprog (from MATLAB) to solve this problem, for exhaustive enumeration solve it by enumerating through the discrete

variables and then use linprog to find the continuous variables. For branch and

bound use linprog or Excel Solver to find the partial solutions.

   Problem 2 is a discrete nonlinear optimisation problem. For branch and bound use fmincon or Excel Solver to find the partial solutions.

   Write a report including all of the followings for each problem:

   For exhaustive enumeration method: how many evaluations were needed for  exhaustive enumeration (1 mark)? Submit your MATLAB code for exhaustive

enumeration (2 mark). Find the optimal solution (1 mark).

   For branch and bound method: What path did the search take for branch and  bound (1 mark)? How many partial nodes were needed for branch and bound

(1 mark)? Draw the trees for branch and bound (3 mark). Find the optimal

solution (0.5 mark).

   For self-assessment: after completing the assignment self-assess your work

according to the marking criteria, give a final mark and reason (require to

explain why you give this mark). (0.5 mark)

Problem 1 (10 marks)

Minimise:

f = 2x1  − 6x2  + 3x3  + 4x4  + 7x5  + 3x6  + 2x7

Subject to:

g1  = x2  + 5x3  + 3x4  − x5  + 2x6  + 3x7   ≥ 65

g2  = −6x1  − 3x2  − 2x3  + x4  + 2x5  − 2x6  ≥ −73

g3  = −7x1  − 4x2  + 3x3  − 4x4  + 3x5  − 2x6  − x7  ≤ −66

x1, x2  ∈ {2,5,7,8}, x3, x4  ∈ {3,4,6}

x5, x6  ≥ 0, x7  ∈ R