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$ Commented Apr 22, 2021 at 9:07
  • $\begingroup$ Thank you, it should be fixed now. $\endgroup$ Commented Apr 22, 2021 at 9:18

2 Answers 2

Reset to default
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$ Commented Apr 22, 2021 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$ Commented Apr 22, 2021 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$ Commented Apr 22, 2021 at 12:30
  • $\begingroup$ Yes I completely missed that. I will refer to your answer in mine (and upvote yours on the way) $\endgroup$ Commented Apr 22, 2021 at 12:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.