I have an optimization problem that I'm trying to cast as a linear program. However, I have an objective function of the form$$\begin{array}{ll} \text{maximize} & a_1 x_1 - a_2 \lvert x_1\rvert\\ \text{subject to} & \color{gray}{\text{(constraints)}}\end{array}$$I tried doing the classic linear reformulation using a replacement variable $x_1'$ and adding the constraints:$$x_1 - x'_1 \le 0$$$$-x_1 - x'_1 \le 0$$The problem that I ran into is that the solutions seem to be constraining $x_1$ to positive values, even when they obviously should be negative. Looking at the docs I have on this, it seems that this is because the assumption is that all values of it will be maximized or minimized in the same direction and if you break this assumption then you're forced to utilize the M/ILP method with binary determiners in order to solve this.I haven't found any discussion on the limitation of using the variables $x_1$ and $x'_1$ in the objective function. Is it possible to do what I want without resorting to ILP?
Is it possible to use both the absolute value and the actual value of a variable in a linear objective function?
optimization;linear programming
$$\begin{array}{ll} \text{maximize} & a_1 x - a_2 | x |\\ \text{subject to} & \color{gray}{\text{(linear constraints)}}\end{array}$$where $a_1, a_2 \in \mathbb R$ are given. Writing as a minimization problem,$$\begin{array}{ll} \text{minimize} &  a_2 | x | - a_1 x\\ \text{subject to} & \color{gray}{\text{(linear constraints)}}\end{array}$$The objective function to be minimized is$$f (x) := a_2 |x| - a_1 x = \begin{cases} -(a_1 + a_2) \, x & \text{if } x \leq 0\\ \,\,\,\,(a_2 - a_1) \, x & \text{if } x \geq 0\end{cases}$$If $a_1, a_2 \geq 0$, then $f$ is convex. In that case, the epigraph of $f$ is also convex and can be defined by the intersection of half-spaces, as follows$$\left\{ (x,y) \in \mathbb R^2 \mid y \geq (a_2 - a_1) \, x \land y \geq -(a_1 + a_2) \, x \right\}$$and we have the following linear program in $x, y \in \mathbb R$$$\begin{array}{ll} \text{minimize} & \,\,\,\, y\\ \text{subject to} & \,\,\,\,(a_2 - a_1) \, x - y \leq 0\\ & -(a_1 + a_2) \, x - y \leq 0\\ & \,\,\,\,\,\color{gray}{\text{(linear constraints on } x)}\end{array}$$