# LP how to sum up positive free variables and negative free variables separately?

For an LP problem where $$x_1,\dots,x_n$$ are free variables (which may take positive or negative values), I want to bound the sums of $$a_i\cdot x_i$$ where $$x_i>0$$, and where $$x_i<0$$.

I suspect this requires MIP with a sign variable for each $$x_i$$.

Any pointers or suggestions would be appreciated.

• Hi Henry, welcome to OR.SE, I think you should use some binary variables to first split the positive and negative variables and then some upon those variables (I assume that $a_i$s are constant-coefficient). Dec 13 '19 at 22:10
• thanks for your comment. i think this is the only approach. the a[i]'s are constant and can be positive or negative. Dec 15 '19 at 20:18

This can be done using the standard trick of splitting each free variable into the difference of two nonnegative variables:

$$x_{i}=u_{i}-v_{i}$$

where $$u \geq 0$$ and $$v \geq 0$$.

$$\sum_{i=1}^{n} a_{i} \max(x_{i},0) \leq b$$

with $$a \geq 0$$, then this can be written as

$$\sum_{i=1}^{n} a_{i} u_{i} \leq b.$$

For the constraint

$$\sum_{i=1}^{n} a_{i} \min(x_{i},0) \geq -b$$

with $$a \geq 0$$, use

$$\sum_{i=1}^{n} a_{i} v_{i} \leq b.$$

Note that it's easy to formulate related constraints that can't be formulated using LP. For example, a constraint like

$$\sum_{i} a_{i} \max(x_{i},0) \geq b$$

with $$a_{i} \geq 0$$ is nonconvex and thus can't possibly be represented with LP. In that case, you might formulate the problem using 0-1 integer variables to encode whether variables are positive or negative.

• Just to be clear, "can't possibly be represented with LP" means "requires binary variables and turns the LP into a MILP". Dec 13 '19 at 22:51
• thank you for the informative response. this clarifies the problem and helps me out. Dec 15 '19 at 20:17