I have intermediate knowledge of optimization and mathematical modeling I have this constraint. I know how to model it with integers (which leads to a mixed-integer linear program). However,I was wondering if there is a way to avoid integer variables.

let: $x_1, x_2$ have undefined signal, they can be positive or negative, but both of them are bounded by an upper and lower limit $$ x_1 = x_{1}^+ + x_1^-\\ \underline{x}_1 \lt x_1 \lt \bar{x}_1 \\ \underline{x}_1 \le x_1^- \le 0, \quad \quad 0 \le x_1^+ \le \bar{x}_1 $$ similarly $$ \\ x_2 = x_2^+ + x_2^- \\ \underline{x}_2 \lt x_2 \lt \bar{x}_2 \\ \underline{x}_2 \le x_2^- \le 0, \quad \quad 0 \le x_2^+ \le \bar{x}_2 $$

These above are just definitions. Now what I want to do is: $$ x_1 \times x_2 \ge 0 $$ which basically means: $x_1$ and $x_2$ must have the same sign or be zero Another way to describe this constraint is or: $$ x_1^+ > 0 \Rightarrow x_2^- = 0 \\ x_2^+ > 0 \Rightarrow x_1^- = 0 $$

I know how to do it with auxiliary integer variables; I was trying to avoid integers in my formulation to continue using a QP or an LP solver.

I tried a big-M constraints and failed. I mention it here to show my work, and save you the effort of exploring it: $$ x_1^- +M\cdot x_2^+ \le 0 $$ This is wrong because it forces $x_2^+$ to be always $0$, even when $x_1^-=0$

$$ \frac{x_1^-}{\underline{x}_1} -\frac{x_2^+}{\bar{x_2}} \le 0 $$ Normalize both variables to handle a percentage, or a surrogate between 0 and 1. Not effective either because it allows $x_2^+$ to be near its upper bound, while $x_1^-$ is slightly below zero.

  • 1
    $\begingroup$ or.stackexchange.com/questions/tagged/linearization $\endgroup$ – Rodrigo de Azevedo Aug 15 '19 at 7:20
  • $\begingroup$ Do you have an objective function? It often helps making constraints easier. Small example: constraint: $2x_1+x_2=8$. It is difficult to find a unique solution. But with max $x_1+x_2$ it is obvious that the (optimal) solution is $(x_1,x_2)=(0,8)$ $\endgroup$ – callculus Aug 15 '19 at 14:02
  • $\begingroup$ The cost function is quite complicated and large; these 2 variables and the constraint I'm talking about are a part of a large optimization problem. What I can tell you, though, is that the cost function is quadratic; I am using GUROBI's QP solver It has just occurred to me that I can achieve my goal with two auxiliary variables, and a penalty on their product. I will explain this in a separate answer below $\endgroup$ – user3730981 Aug 16 '19 at 9:29

It has just occurred to me that I can achieve my goal with a penalty on their product.

$$ Penalty = M\cdot(-x_2^- \times x_1^+) $$

Where $M$ is large enough. Doesn't this qualify as a quadratic cost term?

  • $\begingroup$ It appears that this cost term corresponds to a Q matrix which is NOT positive-semidefinite. I guess I have to go with auxiliary integer variables $\endgroup$ – user3730981 Aug 17 '19 at 7:24

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.