QUESTION $2(60$ points$)$:

The Postgraduate Education Institute $($LEE$)$ at Istanbul Technical University $($ITU$)$ has received applications from $12$ candidates for the $2024-2025$ Fall Master's Degree programs. As shown in the table below, each candidate may have applied to multiple programs.

To manage time efficiently, LEE plans to conduct group interviews based on shared program applications, where candidates who applied to the same program are interviewed together. The interviews are set to start at $9$ am $.$ The applicants are expected to be in the waiting room at the Faculty of Management until the results are announced when the interviews are completed. Each interview session lasts $30$ minutes, and due to limited waiting room space, the goal is to minimize the number of candidates entering and exiting the interview room between sessions. $($Tip: If M$3$ comes after M$2,$ A$1$ and A$10$ will exit, then A$3,$ A$4$ and A$11$ will enter the meeting room. There will be a crowd of $5$ applicants in total.$)$

M$1$: Big Data and Business Analytics

M$2$: Engineering Management

M$3$: Industrial Engineering

M$4$: Business Administration

M$5$: Management Engineering

Applicants

a$.$ Formulate this scenario as an Integer Programming $($IP$)$ model to optimize the scheduling of candidate interviews.

b$.$ Solve the model using Nearest Neighbor Heuristic.

c$.$ Solve the model using Cheapest Insertion Heuristic.

d$.$ Solve the model using Branch $\backslash$& Bound method. $($Use LIFO$)$