I want to solve the following optimization problem
$$\begin{array}{ll} \text{minimize} & | c^\top x |\\ \text{subject to} & A x \leq b\end{array}$$
Without the absolute value, this a standard form for linear programs. Can such a problem be transformed to an ordinary linear program?
Alternatively, by observing that $|c \cdot x|= \max \{c^T x, -c^T x\}$,
$$\min_x |c\cdot x| \text{ subject to } Ax \le b$$
can be rewritten as
$$\min_x \max \{c^T x, -c^T x\} \text{ subject to } Ax \le b$$
which is equivalent to
$$\min_{x, z} z$$
subject to
$$z \ge c^Tx$$
$$z \ge -c^Tx$$
$$Ax \le b$$
which is a linear program.
This works because at the optimal value, $z$ will take one of the value of $c^Tx$ or $-c^Tx$, it takes the value that is bigger.
This is possible by introducing 2 new variables, $t_1,t_2$, and adding a few constraints:
$\begin{align} \min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\ t_1&\geq 0 \\ t_2&\geq 0 \\ Ax&\leq b \end{align}$
Why does this work? The main idea is that an optimal solution must set at least one of $t_1,t_2$ to $0$. First suppose $c\cdot x \leq 0$. This means $0\leq t_1\leq t_2$, so the minimum of $t_1+t_2$ is attained by setting $t_1=0$ and $t_2=-c\cdot x$ and so $t_1+t_2 = -c\cdot x = |c\cdot x|$. Otherwise, $c\cdot x>0$ and so $0\leq t_2 < t_1$, so the minimum of $t_1+t_2$ is attained by setting $t_2=0$ and $t_1=c\cdot x$ and so $t_1+t_2 =c\cdot x =|c\cdot x|$.
Note that this does not work for maximization problems. Replacing min by max makes the program above unbounded (suppose there is a feasible solution with $t_1=a$ and $t_2=b$. Then there is a feasible solution with $t_1=a+C$ and $t_2=b+C$ for any $C\geq 0$).
I'm not aware of any similar formulation for LP problems, but this is solvable in ILP problems by maximizing $T$ under the disjunctive constraint $T= c\cdot x \vee T= -c\cdot x$. (disjunctive constraints can be modeled with a binary decision variable)
I would like to suggest a different angle using the epigraphical relaxation of the absolute value. In particular,
$$ |z| = \min_{|z|\leq t}t = \min_{-t \leq z \leq t}t $$
Using this observation, the optimization problem:
$$ \operatorname*{Minimize}_{x, Ax \leq b} |c^\top x| $$
is equivalent to
$$ \operatorname*{Minimize}_{x, Ax \leq b} \min_{-t \leq c^\top x \leq t}t, $$
that is
$$ \operatorname*{Minimize}_{x,t \,{}:{}\, Ax \leq b,\ -t \leq c^\top x \leq t} t, $$
which is an LP.
