Trying to learn about integer programming in quarantine and I've come across a problem that stumped me. I searched the net but couldn't see anything similar and would appreciate another set of eyes on how to approach it.
Turn the given model in to a binary mixed integer linear programing
model:$\operatorname{Max} z=a(x)+2 b(y)$
s.t $\quad x, y \geq 0$
At minimum two thirds of the given constraints apply:
$$2 x+y \leq 16, \quad x+y \leq 9, \quad x+3 y \leq 12$$
$$a(x)=\begin{cases}10+3 x, & \text{if $0 \leq x \leq 4$}, \\ 14+2 x, &\text{if $x \geq 4$},\end{cases} \quad
b(y)=\begin{cases}8+y, &\text{if $0 \leq y \leq 3$} \\ 2+3y, &\text{if $y \geq 3$}\end{cases}$$
It hints to consider making use of multiple $x$ and $y$ variables and I know that if I want to try linearizing the problem I should go with $b(y)$ due to $y$ having a coefficient of $3$ in the third function.
Best Answer
You can do it with four binary variables. For $i\in\{1,2,3\}$, let binary variable $z_i$ indicate whether constraint $i$ is satisfied, and impose linear constraints \begin{align} 2x+y-16&\le M_1(1-z_1)\\ x+y-9&\le M_2(1-z_2)\\ x+3y-12&\le M_3(1-z_3)\\ z_1+z_2+z_3&\ge 2 \end{align} The original constraints imply upper bounds $x\le 9$ and $y\le 9$, so you can find good values for the $M_i$ constants based on that. For example, take $M_1=2(9)+9-16=11$.
For $a(x)$, the piecewise linear function is concave, so the maximization objective means that you can replace $a(x)$ with a variable $u$ and impose linear constraints \begin{align} u&\le 10+3x\\ u&\le 14+2x \end{align}
For $b(y)$, the piecewise linear function is not concave. Replace $b(y)$ with a variable $v$, introduce a binary variable $z_4$ to indicate which segment is used, and impose linear constraints \begin{align} 0z_4+3(1-z_4)\le y&\le 3z_4+9(1-z_4)\\ 0\le v-(8+y)&\le M_4 z_4\\ 0\le v-(2+3y)&\le M_5(1-z_4) \end{align}