2
$\begingroup$

Assume that we have a LP with the constraint $$ \sum_{j} \left(c_j x_j + |c_j x_j - \alpha_j + \beta_j|\right) \leq y $$ and

$$\alpha_j + \beta_j \leq \lambda_j $$ for all $j$, where the (positive) cost vector $c$ is known, $x_j, \alpha_j$, and $\beta_j \geq 0$ are variables. How do i linearize the absolute values, the usual trick with $|f(x)| \leq y$ would not work because we have multiple absolute values and multiple variables inside the absolute values.

$\endgroup$

1 Answer 1

6
$\begingroup$

Yes, the usual technique applies. Introduce a variable $z_j$ (together with linear constraints) to represent the absolute value, and replace the original constraint with $\sum_j (c_j x_j + z_j) \le y$.

$\endgroup$
2
  • $\begingroup$ The constraint $\alpha_j + \beta_j \leq \lambda_j$ below remains the same right ? $\endgroup$
    – endeavor
    Dec 15, 2022 at 16:38
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – RobPratt
    Dec 15, 2022 at 16:58

Your Answer

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

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