0

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!

RobPratt
  • 45,619
BarkingCat
  • 151
  • Welcome to the forum! Can you type the problem out using MathJax? Also what is the operation between ${\bf{Q}}$ and ${\bf{R}}$? –  Feb 05 '20 at 12:23
  • I will do so later! The operation between Q and R is element-wise multiplication. Aka Hadamard Product https://en.wikipedia.org/wiki/Hadamard_product_(matrices) – BarkingCat Feb 05 '20 at 12:26
  • 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. – Mark L. Stone Feb 05 '20 at 16:13

2 Answers2

2

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.

RobPratt
  • 45,619
  • If I'm reading the image correctly, the nonlinearity would be $\min(x+y,1)$, not $\min(x+y,z)$. – prubin Feb 06 '20 at 00:38
  • OK, I misread "The second element of the vector is just z." as "The second argument of $\min$ is $z$." – RobPratt Feb 06 '20 at 01:10
2

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

prubin
  • 4,923
  • 1
    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. – RobPratt Feb 06 '20 at 01:26