3
$\begingroup$

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.

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

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}

$\endgroup$
2
  • $\begingroup$ Thank you. I don’t quite understand how binary variable z4 is introduced, could you expand on that section? $\endgroup$ – Songaro Apr 22 at 10:05
  • 1
    $\begingroup$ @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]$. $\endgroup$ – Kuifje Apr 22 at 12:21
3
$\begingroup$

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) $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.