# Changing a model in to a mixed integer linear programing model

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.

• It looks like $x$ and $y$ symbols are not consistent. – Kuifje Apr 22 at 9:07
• Thank you, it should be fixed now. – Songaro Apr 22 at 9:18

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}

• Thank you. I don’t quite understand how binary variable z4 is introduced, could you expand on that section? – Songaro Apr 22 at 10:05
• @Songaro His $z_4$ is my $\delta$: if $z_4=1$, then $y$ is in the interval $[0,3]$. And if $z_4=0$, then $y \in [3,9]$. – Kuifje Apr 22 at 12:21

There are many different ways to do this, there are different options here. Here is one, which is definitely not the best, but which is quite natural I guess.

I will only show you how to it for $$a(x)$$, the method is identical for $$b(y)$$.

Define a binary variable $$\delta$$ that takes value $$1$$ if and only if $$x\le 4$$:

$$4(1-\delta)\le x \le 4 +M(1-\delta)$$ $$M$$ is an upper bound on $$x$$. And then define the continuous variable $$a$$ as follows:

$$a = (10+3x)\delta + (14+2x)(1-\delta)$$

Now you have non linear terms (in $$x\delta$$) that you need to linearize, for example like this.

In practice, before using such transformations blindly, be sure to analyze the nature of the function: is it convex or concave, and are you maximizing or minimizing. As mentioned by Rob Pratt, if you are minimizing (maximizing) a convex (concave) function, a much simpler approach is available. Be sure to check his answer.

For the part where at least $$2$$ constraints out of $$3$$ should be satisfied, also please refer to @Rob Pratt's answer, as to my knowledge there is no other way to do it.

Just for pleasure, I also like this method:

Redefine $$x$$ in terms of new variables $$x_1 \ge 0$$ and $$x_2 \ge 0$$ as follows: \begin{align} x&=x_1+x_2+4(1-\delta)\\ x_1&\le 4 \delta \\ x_2& \le 5 (1-\delta) \end{align}

So $$x_1$$ is the range on the first interval $$[0,4]$$, and $$x_2$$ on the second one $$[4,9]$$. And so you can rewrite $$a(x)$$ linearly: $$a = 3x_1+10\delta +2x_2+22(1-\delta)$$

• Note also the part of the question about two thirds of the given constraints. – RobPratt Apr 22 at 12:30
• Yes I completely missed that. I will refer to your answer in mine (and upvote yours on the way) – Kuifje Apr 22 at 12:40