How to transform this linear program into form supported by Python solver

Question

I want to solve the following linear program: $$ min_x \quad \Sigma_{j \in \Omega} c_jx_j \\ subject \space to \quad \Sigma_{j \in \Omega_i} |x_j| \leq 1, i=1,\dots,k $$

($\Omega = \bigcup_{i=1}^k \Omega_i$ and $\Omega = \{1,\dots,n\}$)

All the solvers I have seen (e.g. scipy) expect the following form:

Now, if it wasn't for the absolute value in the condition of my program (i.e. if the condition was $\Sigma_{j \in \Omega_i} x_j \leq 1$), it would be straightforward to write it in the required form. However, with the absolute value, I don't know how to proceed.

From this answer I understand how I can get rid of the absolute value, but I don't see how to put it into the solver.

Any advice would be appreciated.

Answer 1

So in the end I figured it out. Knowing that $$\Sigma_{j \in \Omega_i} |x_j| \leq 1$$ condition is equvalent to: \begin{align} x_i^+ - x_i^- &= x_i \\ x_i^+ &\ge 0 \\ x_i^- &\ge 0 \\ \Sigma_{j \in \Omega_i} (x_i^+ + x_i^-) &\le 1 \end{align}

We can define a new vector: $$c' = [c_1, -c_1,\dots,c_n, -c_n]$$ The optimization objective becomes: \begin{align} min_{x'} \quad \Sigma_{j \in \Omega} c'_jx'_j \\ subject \space to \quad x'_i &\ge 0 \\ \Sigma_{j \in \Omega_i} x'_j &\le 1 \end{align}

After the solution is found, we recover the original coefficients $x_i = x'_{2i - 1} - x'_{2i}$

Answer 2

You can see that $|x|\leq 1$ is same as $x \geq -1$ and $x \leq 1$. Now you can use the matrix $A_{ub}$ and $b_{ub}$ to capture these while passing to the solver.