I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:


max $\sum\_{i=1}^{k}{p(\vec \alpha \cdot \vec c\_i)}$


$s.t. $


$|\alpha\_j| \le 1$ 


Where p(x) = 2x if x < 0, x otherwise, and $ \vec c$ is a constant


The p(x) function is what's troubling me, since one can only determine x's sign after an assignment of $\vec \alpha$. How can I remove the function p from the objective and express this objective equivalently as a linear combination of the variables?


Thank you!



Linear programming piecewise linear objective
Sorry for making you wait 14 hours unnecessarily but you are partially guilty yourself: if you posted a correct and full version of the question from the beginning, you would get the answer in 5 minutes. Keep it in mind when you ask a question on a public forum next time.


Your problem is equivalent to maximizing the linear expression $\sum\_i y\_i$ under the linear restrictions $\alpha\_j\ge -1$, $\alpha\_j\le 1$, $y\_i\le c\_i\cdot\alpha$, $y\_i\le 2c\_i\cdot\alpha$. It is as simple as that but it is crucial that your $p$ is concave and that you maximize.


