An answer to this question on Stack Overflow.

Question

I'm currently using lp_solve and its R API to set and solve a linear programming problem.

For the purpose of this question, setting up a much simpler linear programming problem is useful, so let we have this toy example which you're encouraged to play with:

 minimize     3 x1 -   x2
 subject to    -x1 + 6 x2 - x3 +   x4 >= -3
                     7 x2      + 2 x4 <=  5
                x1 +   x2 + x3        >=  1
                            x3 +   x4 <=  2

Moreover, x1, x2, x3 and x4 shall be integers.

This can be solved very easily, but what if I need to add a constraint which says that:

abs(x1) + abs(x2) + abs(x3) + abs(x4) <= 3

How would you add this constraint and/or how would you deal with the solution to comply with such additional constraint?

Answer

Your problem is currently

minimize     3 x1 -   x2
 subject to    -x1 + 6 x2 - x3 +   x4 >= -3
                     7 x2      + 2 x4 <=  5
                x1 +   x2 + x3        >=  1
                            x3 +   x4 <=  2

To add the constraint

abs(x1) + abs(x2) + abs(x3) + abs(x4) <= 3

Introduce some extra variables and rewrite the constraint:

 x1<=z1
-x1<=z1
 x2<=x2
-x2<=z2
 x3<=z3
-x3<=z3
 x4<=z4
-x4<=z4
z1+z2+z3+z4<=3

The z variables will only bind on the positive (absolute) values of the x variables.