1

I have to cope with a constraint of the form (1) in the following problem:

$$\begin{align}\max\quad& x+y\\ \text{s.t.}\quad& x + y \leq \max \{x,y\} &(1)\\ &0 \leq x \leq U_x&(2)\\ &0 \leq y \leq U_y&(3)\\ \end{align}$$

In the following link you can find an approach but I don't understand it.

https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/

I don't understand: what is $S^+$, $S^-$ and how would a penalization look like? (I refer to the text: "The max function can be linearized as follows: ..." in the reference).

I would be grateful if somebody could help.

The linked figure shows the problem in LP Format and the solution.

nathan.j.mcdougall
  • 1,854
  • 16
  • 22
Clement
  • 113
  • $S^+$ and $S^-$ represent the positive and negative parts of $A-B$ respectively. So if $A-B\geq 0$, then $S^+=A-B$ and $S^-=0$, but if $A-B<0$, then $S^+=0$ and $S^-=B-A$. Thereby, $|A-B|=S^+ + S^-$ and $A-B=S^+-S^-$. Or at least, that's the idea. It will only work, as the website says, if you penalize $S^\pm$ in the objective function.

    See also https://optimization.mccormick.northwestern.edu/index.php/Optimization_with_absolute_values

     – nathan.j.mcdougall Jan 23 '19 at 22:51
  • Thank you very much for the response. I implemented the problem in cplex lp-format. The problem is solved only if I fix S+ or S- to zero (the correct one). How could the penalization term, in a maximization objective function, look like so that either S+ xor S- becomes zero at the optimum? If I add i.e. the term - (S+ * S-) to the maximization objective I end up with a nonlinear problem, which of course is not desirable. – Clement Jan 24 '19 at 16:13
  • I think you can just add $-(S^+ +S^-)$ to the objective, you don't need it to be a product. The reason is that since $A-B=S^+-S^-$, and $S^+,S^-\geq 0$, you can get one of the two to be zero if you minimize the sum of both magnitudes/maximize the negative sum. – nathan.j.mcdougall Jan 24 '19 at 19:02
  • Unfortunately, add −(S+ + S−) to the objective doesn't solve the problem. In my first posting I added a figure (click on the link "¨The linked figure ...") showing an example in LP format. The solution should be 100 (=A) but the optimizer sets S+ = S- = 20 instead of S- =0 and returns 80 as the optimum. Is my implementation incorrect? – Clement Jan 24 '19 at 21:31

2 Answers2

1

The reformulation in the link isn't guaranteed to work. In this case, it doesn't, because the feasible region is not convex. You cannot express a non-convex feasible region with linear constraints.

To see that it is not convex, note that if $x\geq y$, then $x+y\leq x$, so $y=0$. Otherwise, $y>x$, so $x+y\leq y$ and then $x=0$. Therefore, either $x=0$ or $y=0$.

We have feasible solutions of $(x,y)=(U_x,0)$ and $(x,y)=(0,U_y)$. If the feasible region were convex, a convex combination of those would be feasible, like $(x,y)=\frac{1}{2}(U_x,U_y)$. However, it's not feasible unless $U_x=0$ or $U_y=0$.

So for general $U_x,U_y$, you can't use this reformulation. Instead, you'll probably want to introduce a binary variable, and solve a mixed integer programme. Or, in this case, by inspection.

nathan.j.mcdougall
  • 1,854
  • 16
  • 22
  • Thank you very much. That explains why Cplex doens't deliver the result I would expect (like to have). – Clement Jan 24 '19 at 22:32
0

Hello I hope it is not too late; the penalty could be representative like this:

max x + y
x <=s1 + s2
y <=s1 + s2
s1 >= x - y
s2 >= y - x
s1 - bigMb <= 0
s2 - bigM(1-b) <= 0
0 <= x <= Ux
0 <= y <= Uy

where b is binary variable

Jorge Cordova
  • 1