Deadline: April 28, 2023. Submissions after this date will incur late submission penalties as indicated in the first lecture.

Instructions

Answer all questions. Submit your assignment as one Jupyter notebook file (not a DOC/ DOCX/ODT/ZIP/PDF file) via the module Brightspace page. Please ensure that together with the code, you provide sufficient details of your solutions in markdown cells. In particular,  please  explain  what  your  decision  variable  means,  what  is  your  objective function etc.

This assessment should be completed individually. Any evidence of plagiarism will be reported to the CS plagiarism committee and it can result in a Fail grade. In particular, the use of ChatGPT, Chegg or other such tools for this assignment is strictly prohibited.

Question 1  (20 points)

Consider the following binary integer program.

Maximise 12x1 + x2 + 10x3 + 2x4

s . t . 16x1 + 2x2 + 10x3 + 9x4 ≤ 20

xi ∈ {0,1 } for i = 1, …,4

Use the branch-and-bound method to find an optimal solution to this problem. You can use Julia/JuMP and a solver to solve the LP relaxations of the subproblems resulting from fixing some decision variables at 0 or 1. Fix the variables in the order x1, x2, x3, x4.

Please do not use the Julia/JuMP and the solver to directly solve the ILP itself.

Question 2  (30 points)

Rectangle stabbing problem: In this problem, we are given a set of n axis-parallel rectangles R in the two-dimensional plane. Our goal is to compute a minimum set of lines L that stab all input rectangles. We call a rectangle stabbed if a line l ∈ L intersects both of its horizontal or both of its vertical edges. The lines have to be either horizontal or vertical, but they can be anywhere in the plane . Your first task is to discretise this problem, i .e . , find discrete and finite number of possibilities for the lines such that the optimal solution will still be a subset of those lines . Then, formulate the discrete minimisation problem as an integer linear program . For the two instances shown below, compute the optimal number of lines using Julia/JuMP and your ILP formulation.

Question 3 (20 points)

Maximum Weight Bipartite Matching: Consider a bipartite graph G. Each edge e of G has an associated positive weight we . A matching is a set of edges no two of which share an endpoint. The goal of the maximum weight bipartite matching problem is to find a matching of maximum weight . Formulate this problem as an integer linear program . For the instance shown below, solve the integer linear program using Julia/JuMP. Consider the linear programming relaxation of the ILP and solve it using Julia/JuMP. What is the ratio between the optimal ILP and LP solution for the instance below?