2
$\begingroup$

I am trying to solve an optimization problem where the constraint contains absolute values and I am not sure how I can express this in a 'Pyomo-friendly' way.

Consider the following optimization problem:

$$\max_{b_{n}} \sum_{n} \space a_{n}(b_{n} - c_{n})$$

subject to $a_{n} > 0$ and $b_{n} = \begin{cases} c_{n}, & |b_{n} - c_{n}|\leq \epsilon \\ b_{n}, & |b_{n} - c_{n}| > \epsilon \end{cases}$.

As this is not a linear constraint, my guess is that this is not solvable. I also found this question where it is mentioned that there are some modelling tricks.

Improve this question
$\endgroup$
5
  • $\begingroup$ Is $a_n>0$ for all $n$? $\endgroup$
    – RobPratt
    Nov 28, 2022 at 19:59
  • $\begingroup$ Yup, I will edit the post. $\endgroup$
    – BenBernke
    Nov 28, 2022 at 20:03
  • $\begingroup$ What are the optimization variables? $\endgroup$
    – Rodrigo de Azevedo
    Nov 29, 2022 at 11:11
  • $\begingroup$ @RodrigodeAzevedo The $\max_{b_n}$ suggests that the $b_n$ are the variables and everything else is a constant, but my formulation works even if $c_n$ is also a variable. $\endgroup$
    – RobPratt
    Nov 29, 2022 at 13:11
  • $\begingroup$ @RobPratt Yes, indeed, but the "subject to $a_n > 0$" suggests something else. This confusion is avoided when people follow the convention of picking the first letters of the alphabet for knowns and the last letters of the alphabet for unknowns. $\endgroup$
    – Rodrigo de Azevedo
    Nov 29, 2022 at 13:53

1 Answer 1

Reset to default
4
$\begingroup$

It looks like you want to enforce the disjunction $$(b_n - c_n < -\epsilon) \lor (b_n - c_n = 0) \lor (b_n - c_n > \epsilon).$$ You can instead enforce the following disjunction: $$(b_n - c_n \le -\epsilon) \lor (b_n - c_n = 0) \lor (b_n - c_n \ge \epsilon).$$ Assume finite bounds $L \le b_n - c_n \le U$. Introduce binary variables $x_n$, $y_n$, and $z_n$, and impose the following linear constraints: \begin{align} x_n + y_n + z_n &= 1 &&\text{for all $n$}\\ Lx_n + 0y_n + \epsilon z_n \le b_n - c_n &\le -\epsilon x_n + 0y_n + Uz_n &&\text{for all $n$}\\ \end{align} Alternatively, omit $y_n$ and instead impose: \begin{align} x_n + z_n &\le 1 &&\text{for all $n$}\\ Lx_n + \epsilon z_n \le b_n - c_n &\le -\epsilon x_n + Uz_n &&\text{for all $n$}\\ \end{align}

Improve this answer
$\endgroup$
3
  • $\begingroup$ Many thanks for the help! I think I am following but I was wondering if you could briefly explain the difference between the lower bound L and the epsilon mentioned in my post. $\endgroup$
    – BenBernke
    Nov 28, 2022 at 20:28
  • $\begingroup$ $L<-\epsilon < 0<\epsilon <U$ $\endgroup$
    – RobPratt
    Nov 28, 2022 at 20:33
  • $\begingroup$ Understood! Very cool solution, thanks a lot. $\endgroup$
    – BenBernke
    Nov 28, 2022 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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