12
$\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$
  • $\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$ – Oguz Toragay Dec 13 '19 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 '19 at 20:18
13
$\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.

| improve this answer | |
$\endgroup$
  • 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 '19 at 22:51
  • $\begingroup$ thank you for the informative response. this clarifies the problem and helps me out. $\endgroup$ – Henry Dec 15 '19 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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