For example, we have an optimization problem

$$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$

and $a_i, b_i, c_i$ are given. How to convert it into a linear program?

I know that if we want to minimize $|x - a|$, we should let minimize $z$ where $z \ge x-a$ and $z \ge -(x-a)$. However, in this case, we want to minimize the weighted sum of absolute value and do not know the sign of $b_i$. Does anyone know how to do it?

  • 4
    $\begingroup$ If the given $b_i$ can be negative, the problem is not convex so you cannot formulate as LP. $\endgroup$
    – RobPratt
    Nov 23, 2023 at 4:23
  • $\begingroup$ if the given bi is negative, we can use the big N method to convert it into a LP, right? $\endgroup$
    – Pique
    Nov 24, 2023 at 5:37
  • 2
    $\begingroup$ Big-M constraints involve binary variables, so the resulting problem would be integer linear programming, not LP. $\endgroup$
    – RobPratt
    Nov 24, 2023 at 14:32
  • $\begingroup$ @Pique, is the problem related to the single/multi-facility location problem? If so, the sign of $b_i$ should be positive and the problem can be formulated as an LP. $\endgroup$
    – A.Omidi
    Nov 26, 2023 at 6:36


Your Answer

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