0
$\begingroup$

The goal is to maximize the objective function, where the decision variable is the vector x = [x,y,z]. It is a binary integer problem (i.e: x,y,z can only take values of 0 or 1). See image for full details:

enter image description here

It seems to be almost solvable with LP because the first part of my objective function is linear (x dot Q*R) (please correct me if I'm wrong in assuming so), but the second part is harder. I have read some stuff online on linearizing an objective function with a min sign: Linearizing min function Problem

Although this is not directly applicable as it is only the first element of the second part of the objective function (denoted as "Decision Vector" (with quotes) in the image) that contains the min operator. The second element of the vector is just z.

Concretely, my main question: is it possible to solve the following integer programming problem, by somehow rewriting the second part using an auxiliary variable to get rid of the "min" operator and make the objective function linear? Also, in the end I want to do this in Python. If there are any implementation tips it would also be greatly appreciated.

Thanks!

$\endgroup$
3
  • $\begingroup$ Welcome to the forum! Can you type the problem out using MathJax? Also what is the operation between ${\bf{Q}}$ and ${\bf{R}}$? $\endgroup$ Commented Feb 5, 2020 at 12:23
  • $\begingroup$ I will do so later! The operation between Q and R is element-wise multiplication. Aka Hadamard Product en.wikipedia.org/wiki/Hadamard_product_(matrices) $\endgroup$ Commented Feb 5, 2020 at 12:26
  • $\begingroup$ Am I correct in understanding that the only decision variables are 3 scalar binary variables? If so, there are only 8 feasible solutions, and brute force enumeration can be used to select the best objective value among of those 8. $\endgroup$ Commented Feb 5, 2020 at 16:13

2 Answers 2

Reset to default
2
$\begingroup$

You can maximize a minimum (or minimize a maximum) without introducing binary variables.

But here you are maximizing the negative of a minimum, which is like maximizing a maximum (or minimizing a minimum). You can do this by introducing a binary variable $b$ that indicates which argument attains the min, as described in this post. Explicitly, introduce a new variable $w$ to represent $\min(x+y,z)$. The following "big-M" linear constraints enforce the desired relationship: \begin{align} w &\le x+y\\ w &\le z\\ w &\ge x+y-M_1(1-b)\\ w &\ge z-M_2 b \end{align} If $b=1$, then $w=x+y$. If $b=0$, then $w=z$. Here, $M_1$ and $M_2$ are (small) constants such that $w \ge x+y-M_1$ and $w \ge z-M_2$ are redundant.

$\endgroup$
2
  • $\begingroup$ If I'm reading the image correctly, the nonlinearity would be $\min(x+y,1)$, not $\min(x+y,z)$. $\endgroup$ Commented Feb 6, 2020 at 0:38
  • $\begingroup$ OK, I misread "The second element of the vector is just z." as "The second argument of $\min$ is $z$." $\endgroup$ Commented Feb 6, 2020 at 1:10
2
$\begingroup$

To linearize $\min(x+y,1)$ (where $x$ and $y$ are both binary), introduce a new variable ($w$, in honor of Rob's answer) with domain $[0,1]$ (not binary; continuous on the unit interval) along with the constraints \begin{align} w &\le x+y\\ w &\ge x\\ w &\ge y. \end{align} If $x=0=y$, the constraints will force $w=0$. If either $x=1$, $y=1$ or both, the constraints (plus the upper bound on $w$) force $w=1$.

$\endgroup$
1
  • 1
    $\begingroup$ Note that $w=\min(x+y,1)$ is equivalent to $w \iff (x \lor y)$. Rewriting in conjunctive normal form somewhat automatically yields the desired constraints: $$ w \iff (x \lor y) \\ (w \implies (x \lor y)) \land ((x \lor y) \implies w) \\ (\neg w \lor (x \lor y)) \land (\neg (x \lor y) \lor w) \\ (\neg w \lor x \lor y) \land ((\neg x \land \neg y) \lor w) \\ (\neg w \lor x \lor y) \land (\neg x \lor w) \land (\neg y \lor w) \\ (1 - w + x + y \ge 1) \land (1 - x + w \ge 1) \land (1 - y + w \ge 1) \\ (x + y \ge w) \land (w \ge x) \land (w \ge y), $$ as @prubin obtained. $\endgroup$ Commented Feb 6, 2020 at 1:26

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.