13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ Dec 13, 2019 at 22:10
  • $\begingroup$ thanks for your comment. i think this is the only approach. the a[i]'s are constant and can be positive or negative. $\endgroup$
    – Henry
    Dec 15, 2019 at 20:18

1 Answer 1

14
$\begingroup$

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$.

If your constraint is

$$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.