Problem $1$: Discrete Optimization

Alice, Bryanna, Chris and Deshmuk are eagerly awaiting for the end of Prof. Rios class to go on vacations.

Their plan right now is to rent a small apartment in Austin, TX$,$ for a period of $6$ weeks, at a total cost of $$6,000.$ The apartment can accommodate at most $2$ people, and the friends are planning on going only over the weekends $($due to their internships$).$ Furthermore, since driving all the way to Austin is not really a piece of cake, the friends also decided not to split the weekends $$ in other words, whomever goes on a weekend stays there for the entire weekend. Their goal is to design a schedule of trips that would maximize their cumulative preference, i$.$e$.,$ the sum of their individual preferences.

To list their preferences, they each rated every weekend with $1,2,$ or $3$ stars, with more stars denoting a more preferred option. This information is gathered in Table $1$ for instance, Alice rated the second weekend with $3$ stars, showing that she would really like to go to Austin in the second weekend. As an example, if Alice goes only on weekeds #$1$ and #$2,$ Bryanna goes only on weekeds #$2$ and #$3,$ Chris goes only on weekends #$3$ and #$4,$ and Deshmuk goes on weekeds #$4,$ #$5$ and #$6,$ then the cumulative preference of this schedule is: $(1+3)+(2+2)+(3+2)+(2+1+1)=17.$

The last column of Table $1$ also contains a budget for each person, indicating how much each of them is willing to spend on rental costs. The budgets should never be exceeded. To split the cost of the rental, they decided to use a very simple scheme. With $6$ weekends and a capacity of $2,$ there are basically $12$ spots. This would mean a charge of $$6,000/12=$ $$500$ per person per weekend. Each person should be responsible for paying their own utilized slots, and the cost of any remaining un$-$utilized spots should be split evenly among the four of them. For instance, if Alice, Bryanna and Chris each go for three weekends and Deshmuk only goes for two, the first three friends would each pay $$1,500+$ $$500/4,$ and Deshmuk would pay $$1,000+$ $$500/4.$ Finally, to maintain some crude fairness, the friends also decided that each of them

should

get to go at least twice.

$1.(20$ points$)$ Construct a discrete linear optimization model that can solve the problem faced by the four friends. Solve your model. What is the optimal solution? Remember not to use any IF$,$ MAX, MIN, etc statements.

$2.(5$ points$)$ Alice would like to ensure that if she gets the second week, she also gets the third $($so that her family can join her in Austin$).$ Implement this change in your model from part $1$ so it remains linear. What is the new schedule and what is the resulting total preference?

$3.(5$ points$)$ Deshmuk would like to request that if he does not get the first weekend, he should get the fifth one. Implement this change in your model from part $1$ so it remains linear. What is the new schedule, and what is the resulting total preference?

$4.(5$ points$)$ Deshmuk states that his aggregate preference for the schedule would increase by $2$ stars if he goes to Austin on both weekends $4$ and $5.$ Implement this change in your model from part $1$ so it remains linear. What is the new schedule, and what is the resulting total preference?

$5.(5$ points$)$ Alice and Chris would like to go together at least once during the first three weekends. Implement this change in your model from part $1$ so it remains linear. What is the new schedule, and what is the resulting total preference? in excel