T11-1.Rmd

---
title: "Tutorial 11: Integer Optimization"
author: "BT1101 Student. REPLACE WITH YOUR NAME"
date: 'Practice Only'
output: html_document
---

## Submission Instructions

- Select `output: html_document`.
- Include all code chunks, so include `echo=TRUE` in all chunks.
- Replace the placeholder text, "Type your answer here.", with your own.
- Submit *only* the required question for grading (Part 2: Submission). You can delete everything else for that submission. Remember to include any `library('package_name')` statements that you'll need to run your code and future reproduction. 
- Rename your R Markdown file `T[X]_[MatricNumber].rmd`, and the output will automatically be `T[X]_[MatricNumber].html`. 
- Tutorial 11 will be for self-practice only. Questions will be discussed during lab and tutorial sessions.
- **It is important to be able to code and produce your Rmarkdown output file *independently*.** You are responsible for de-bugging and programming in the practical exam.

## Preparation

```{r load-libraries, echo=TRUE, warning = FALSE, message = FALSE}
# load required packages
# install any package below if it's first time loaded in your computer.
library(lpSolve)
```

Please use the following table template for both Parts 1 and 2, which comes from the Farmer Jean example in lecture. This table should exist OUTSIDE any `r` code chunks in order to format properly since it's markdown (html in this case) and not R. Here, we use a pair of '\$'s to enter/exit math mode (this is LaTeX, for those of you who are familiar with and which I used to produce the lecture handouts), which allows us to type symbols like $X_1$, $\leq$ for the "less than or equals" sign and $\geq$ for the "greater than or equals" sign. Use $\,$ (thin space), $\;$ (medium space), $\quad$ (large space, equivalent to curent font size), $\qquad$ (two large spaces) for spacing, so you can leave a blank for decision variables with coefficients of 0. 
(Note: don't put two \$'s next to each other. Always put a space in between.). 

Maximize total profit using decision variables $X_1$, $X_2$ | Profit = 0.15 $X_1$ + 0.40 $X_2$
--- | --- 
Subject to |  
Budget Constraint | 0.20$X_1$ + 0.70$X_2$ $\leq$ 100
Space Constraint | $X_1$ + $X_2$ $\leq$ 200
Non-Negativity Constraint 1 | $X_1$ + $\quad$ $\geq$ 0
Non-Negativity Constraint 2 | $\quad$ + $X_2$ $\geq$ 0

You may also refer to: https://github.com/adam-p/markdown-here/wiki/Markdown-Cheatsheet#tables for additional information regarding table formatting. From the professor's experience, it takes a while to get used to making tables in Markdown, and even minor changes may break the table. The most common mistakes are: 

- not having a blank line before and a blank line after each table, 
- not having the correct number of \|'s, 
- not ending Math mode correctly, and 
- putting two \$s next to each other. 

The professor will not entertain emails regarding table formatting questions. Also note that for this assignment, please *IGNORE* integer requirements, i.e., just use real number (e.g. fractional answers) if/when they come up. We shall leave it to the last tutorial assignment for integer optimization.

## Part One: Lab Session Completion and Discussion

### Question 1 


John is interested in buying ads to market his new startup. He sees the following options:

Ad | Cost per ad | Reach | Limits
--- | --- | --- | ---
Radio Ad | \$100 | 500 | 40 
Newspaper Ad | \$250 | 2000 | 10
Social Media Ad | \$50 | 300 | 80

The "limits" in the table above are imposed by each advertiser, so the Newspaper will only run a maximum of 10 Newspaper Ads. Reach is an estimated number of people that the ad will reach, per ad that John buys (e.g. if he buys 1 Radio ad, it will reach 500 people. If he buys 2, it will reach 1000 people.)


John has a budget of \$5000, and wants to find out how many ads he should purchase to maximize his total reach.



Q1a) Identify the decision variables, objective function and constraints. Write out the optimization problem in a table.


<p style="color:red">**Type your answer here.**</p>

Maximize total reach using decision variables $X_1$, $X_2$, $X_3$ | Profit = 500 $X_1$ + 2000 $X_2$ + 300 $X_3$
--- | --- 
Subject to |  
Budget Constraint | 100$X_1$ + 250$X_2$ + 50$X_3$ $\leq$ 5000
Radio Limit Constraint | $X_1$ + $\quad$ + $\quad$ $\leq$ 40
Newspaper Limit Constraint | $\quad$ + $X_2$ + $\quad$ $\leq$ 10
Social Media Limit Constraint | $\quad$ + $\quad$ + $X_3$ $\leq$ 80
Non-Negativity Constraint 1 | $X_1$ + $\quad$ + $\quad$ $\geq$ 0
Non-Negativity Constraint 2 | $\quad$ + $X_2$ + $\quad$ $\geq$ 0
Non-Negativity Constraint 3 | $\quad$ + $\quad$ + $X_3$ $\geq$ 0
Integer Constraints | $X_1$, $X_2$, $X_3$ all integers

Q1b) Write R code to solve this problem. What is the optimal solution, and what is the value of the objective function that this optimal solution?


<p style="color:red">**Type your answer here.**</p>


```{r q1b-lp, echo=TRUE}
# type your code here
objective_fn1 <- c(500, 2000, 300)
constraint_mat1 <- matrix(c(100, 250, 50, 1, 0, 0, 0, 1, 0, 0, 0, 1),
                         ncol=3,
                         byrow=TRUE)
constraint_dir1 <- c("<=", "<=", "<=", "<=")
constraint_rhs1 <- c(5000, 40, 10, 80)

lp_solution1 <- lp(direction="max",
                   objective_fn1,
                   constraint_mat1,
                   constraint_dir1,
                   constraint_rhs1,
                   int.vec=c(1, 2, 3))

print(lp_solution1$solution)

print(lp_solution1)
```


## Part Two: Self-Practice for Tutorial Discussion

### Question 2


As I briefly mentioned in class that empirical evidence shows that college students are quite strategic to allocate their efforts on their curriculum. Let's see a college curriculum management problem in a simpler version. Ross, a freshman college student, is deciding which courses he should take to complete his degree plan. He needs at least 12 credits to get his degree.

The program offers the following courses to prospective business analytics students: Business Analytics (**BT**), Computer Science (**CS**), Statistics (**ST**) and Dissertation (**DT**), along with associated effort levels (hr/week) and pre-requisites. The pre-requisites for each course must be fulfilled before students are allowed to take that course. Ross has also indicated his personal interest (utility) in each course.


Course | Credit | Pre-requisites | Effort | Interest
--- | --- | --- | --- | ---
BT1 | 2 | - | 6 | 10
BT2 | 4 | ST *or* BT1 | 7 | 8 
CS1 | 3 | - | 9 | 2
CS2 | 3 | CS1 | 8 | 5
ST | 4 | - | 10 | 7
DT | 5 | BT1 *and* CS1 | 20 | 6


(Q2a) How would you write out the following constraint as a linear constraint? 

Students must take CS1 before CS2


<p style="color:red">
$X_{CS1}$ - $X_{CS2}$ $\geq$ 0
</p>


(Q2b) Ross says he is working part-time in a coffee shop so he cannot study more than 30 hours per week. Ross says that his goal is to maximize his interest and satisfy the requirements of the degree. 

- Identify the decision variables, objective function, and the relevant constraints. 
- Write them out in a table. 

You may keep the "Pre-requisite" constraints in the form $X_X \pm X_Y \leq = \geq 0$ for this table. **Do not solve the problem yet**.

<p style="color:red">**Type here your answer here.**</p>

Maximize total interest using decision variables $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ | Profit = 10$X_{BT1}$ + 8$X_{BT2}$ + 2$X_{CS1}$ + 5$X_{CS2}$ + 7$X_{ST}$ + 6$X_{DT}$
--- | --- 
Subject to |  
Effort Constraint | 6$X_{BT1}$ + 7$X_{BT2}$ + 9$X_{CS1}$ + 8$X_{CS2}$ + 10$X_{ST}$ + 20$X_{DT}$ $\leq$ 30
Degree Requirement Constraint | 2$X_{BT1}$ + 4$X_{BT2}$ + 3$X_{CS1}$ + 3$X_{CS2}$ + 4$X_{ST}$ + 5$X_{DT}$ $\geq$ 12
BT2 Prerequisite Constraint | ($X_{ST}$ + $X_{BT1}$) - $X_{BT2}$ $\geq$ 0
CS2 Prerequisite Constraint | $X_{CS1}$ - $X_{CS2}$ $\geq$ 0
DT Prerequisite Constraint | ($X_{BT1}$ + $X_{CS1}$) - 2$X_{DT}$ $\geq$ 0
Binary Decision Variables | $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ either 0 or 1


(Q2c) Ok, Ross just admitted that he was simply trying to minimize his effort to get his school done. Rewrite the problem to minimize the overall effort level. 

- Write out the table again. (It should be simplier compared to 2b since part-time working does not play a roll here.)
- If you are not confident of going straight from this table to R, please take the additional step of converting the linear constraints into a "fully spelled-out" constraint with all the $0$s, $1$s and $-1$s such as: <br> $X_X - X_Z \geq 0$ $\implies$ $1X_X + 0X_Y + -1 X_Z + 0 X_A + \ldots \geq 0$ )
- Using R, write a linear program to solve Ross's problem. 

Which course(s) should Ross pick? 

<p style="color:red">**Type here your answer here.**</p>

Minimize total effort using decision variables $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ | Effort = 6$X_{BT1}$ + 7$X_{BT2}$ + 9$X_{CS1}$ + 8$X_{CS2}$ + 10$X_{ST}$ + 20$X_{DT}$
--- | --- 
Subject to |  
Degree Requirement Constraint | 2$X_{BT1}$ + 4$X_{BT2}$ + 3$X_{CS1}$ + 3$X_{CS2}$ + 4$X_{ST}$ + 5$X_{DT}$ $\geq$ 12
BT2 Prerequisite Constraint | ($X_{ST}$ + $X_{BT1}$) - $X_{BT2}$ $\geq$ 0
CS2 Prerequisite Constraint | $X_{CS1}$ - $X_{CS2}$ $\geq$ 0
DT Prerequisite Constraint | ($X_{BT1}$ + $X_{CS1}$) - 2$X_{DT}$ $\geq$ 0
Binary Decision Variables | $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ either 0 or 1

```{r q2c-lp, echo=TRUE}
# type your code here
objective_fn2 <- c(6, 7, 9, 8, 10, 20)
constraint_mat2 <- matrix(c(
  2, 4, 3, 3, 4, 5, 
  1, -1, 0, 0, 1, 0,
  0, 0, 1, -1, 0, 0,
  1, 0, 1, 0, 0, -2),
  ncol=6,
  byrow=TRUE)
constraint_dir2 <- c(rep(">=", 4))
constraint_rhs2 <- c(12, 0, 0, 0)
lp_solution2 <- lp(direction="min",
                   objective_fn2,
                   constraint_mat2,
                   constraint_dir2,
                   constraint_rhs2,
                   binary.vec=c(1:6))

print(lp_solution2$solution)

print(lp_solution2)

```


(Q2d) Let's say school now provides two degree plans:

- Plan A: At least 12 credits. (what you solved in the previous question)
- Plan B: At least one level-2 (such as BT2 or CS2) course and DT.

As to minimize his efforts and get the degree, which degree plan should Ross pick? 

Hint: You have already done the computation for plan A in (2c). Now you need to solve the same minimization problem again with "Plan A 12-credit constraint" replaced with the new constraint of Plan B and then compare such two minimization problems. 


<p style="color:red">**Type here your answer here.**</p>

Minimize total effort using decision variables $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ | Effort = 6$X_{BT1}$ + 7$X_{BT2}$ + 9$X_{CS1}$ + 8$X_{CS2}$ + 10$X_{ST}$ + 20$X_{DT}$
--- | --- 
Subject to |  
Level-2 Constraint 1 | $X_{BT2}$ + $X_{CS2}$ >= 1
Level-2 Constraint 2 | $X_DT$ >= 1
BT2 Prerequisite Constraint | ($X_{ST}$ + $X_{BT1}$) - $X_{BT2}$ $\geq$ 0
CS2 Prerequisite Constraint | $X_{CS1}$ - $X_{CS2}$ $\geq$ 0
DT Prerequisite Constraint | ($X_{BT1}$ + $X_{CS1}$) - 2$X_{DT}$ $\geq$ 0
Binary Decision Variables | $X_{BT1}$, $X_{BT2}$, $X_{CS1}$, $X_{CS2}$, $X_{ST}$, $X_{DT}$ either 0 or 1

```{r q2d-lp, echo=TRUE}
# type your code here
objective_fn3 <- c(6, 7, 9, 8, 10, 20)
constraint_mat2 <- matrix(c(
  0, 1, 0, 1, 0, 0, 
  0, 0, 0, 0, 0, 1,
  1, -1, 0, 0, 1, 0,
  0, 0, 1, -1, 0, 0,
  1, 0, 1, 0, 0, -2),
  ncol=6,
  byrow=TRUE)
constraint_dir2 <- c(rep(">=", 5))
constraint_rhs2 <- c(1, 1, 0, 0, 0)
lp_solution2 <- lp(direction="min",
                   objective_fn2,
                   constraint_mat2,
                   constraint_dir2,
                   constraint_rhs2,
                   binary.vec=c(1:6))

print(lp_solution2$solution)

print(lp_solution2)

```