Question 1.

A store is offering a discount on 800 pairs of basketball shoes in Singapore. The amount of the discount varies and is not revealed to the customer until checkout. The following table shows the potential areas for home delivery service covered by each store.

(a) Formulate an integer programming model that could be used to find the minimum number of stores to open in order to cover customers of all areas for the home delivery service. (15 marks)

(b) Discuss whether the solution of the integer programming problem could be obtained by rounding the solutions generated from the relaxed linear optimization problem. (Your answer shall not exceed 150 words.) (10 marks)

Question 2.

Carlos is a fund manager from investment bank department of Star-Village. He is planning for next years capital budget. There are 6 different projects available for investment. The net present value (NPV) and initial cost required for each project are listed as follows ($ millions):

The total budget for all projects is $250 million.

There are certain conditions of restricting the investment alternatives:

Project 1 cannot be taken unless both project 3 and 4 are also undertaken.

If Project 2 is taken, then Project 5 cannot be taken.

If either Project 1 or Project 5 is taken, they must both be taken.

At least two projects from Project 1, 2, 3 and 4 must be taken.

Formulate a binary integer program that will help Carlos to maximize his final expected return, while satisfying all the given restrictions. (35 marks)

\begin{tabular}{|c|c|} \hline Store Location & Potential Areas Covered \\ \hline L1 & 3,4,6,8 \\ \hline L2 & 1,5,9 \\ \hline L3 & 1,4,7 \\ \hline L4 & 2,6,7 \\ \hline L5 & 3,4,9 \\ \hline L6 & 2,7,9 \\ \hline L7 & 4,8,9 \\ \hline L8 & 1,2,5,6 \\ \hline L9 & 3,6,8 \\ \hline \end{tabular} \begin{tabular}{|l|l|l|l|l|l|l|} \hline Project & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline NPV & 10 & 6 & 15 & 12 & 19 & 21 \\ \hline Expenditure & 50 & 70 & 80 & 65 & 110 & 180 \\ \hline \end{tabular}