4
$\begingroup$

I have a continuous variable $x_t$. A binary variable $b_t$ should be coupled to $x_t$ such that $b_t$ has the value $1$ if $x_t$ has a value greater than $0$ and $b_t$ has the value $0$ if $x_t$ has the value $0$. Any idea how I can do that without including the term $b_t$ in the objective function?

$\endgroup$
9
  • $\begingroup$ This is a FAQ -- frequently asked here and frequently answered here. $\endgroup$ – prubin May 17 at 20:22
  • $\begingroup$ You will have to choose a tolerance as to how close to zero should be considered zero, taking into account solver tolerance, wherein a variable for which the true optimum is exactly zero will not be exactly zero as computed in and returned by the solver. $\endgroup$ – Mark L. Stone May 18 at 0:14
  • $\begingroup$ @prubin I agree this is a FAQ, here is quite a complete answer. But it may be worth answering $x_t=0\; \Rightarrow \; b_t = 0$ (?), which is the hard part, I think. $\endgroup$ – Kuifje May 18 at 6:53
  • $\begingroup$ @MarkL.Stone Thanks for your answer Mark L. Stone. How can I formulate this with equations? $\endgroup$ – PeterBe May 18 at 9:04
  • $\begingroup$ @prubin: Thanks for your comment. Would you mind sending me 2 or 3 links to such questions? I'd highly apprciate this. $\endgroup$ – PeterBe May 18 at 9:16
4
$\begingroup$

I'm only aware of a mechanism that works if there is an upper bound for the continuous variable.

\begin{align}x_{t, \max}\cdot b_t &\geq x_t\\ m\cdot x_t &\geq b_t\end{align}

I used this in answering this question. I'm not aware of a way to solve it for unbounded $x_t$, unless the solver handles floating points infinities correctly. This would need to be tested by solvers. The second equation implements the $x_t < \frac{1}{m}\implies b_t=0 $. If the trueness of $b_t$ is penalized in the objective the second term is unnecessary.

$\endgroup$
5
  • $\begingroup$ Thanks worldsmithhelper for your answer. Basically the continous variable has an upper bound of 1 and a lower bound of 0. Nonetheless I think your approach does not work and is wrong. If x(t) has the value 0.2, then your second equations forces b(t) to have the value 0 which is wrong. $\endgroup$ – PeterBe May 20 at 9:01
  • $\begingroup$ Mhh you are right. You could fix that by multiplying $x_t$ by a sufficiently large numbers. I edited my answer. $\endgroup$ – worldsmithhelper May 20 at 9:03
  • $\begingroup$ Thanks for your answer and effort worldsmithhelper. This solution might work. I will try it. How would your suggested solution change, if the lower bound of x is let's say 0.25 (while the upper bounds remains 1)? $\endgroup$ – PeterBe May 20 at 9:12
  • $\begingroup$ $x_{t,max} = 1$ and $m=4$ $\endgroup$ – worldsmithhelper May 20 at 9:16
  • 1
    $\begingroup$ Thanks worldsmithhelper for your answer. I upvoted and accepted your answer. I really appreciate your tremendous help. $\endgroup$ – PeterBe May 20 at 10:22
4
$\begingroup$

Enforcing $b_t$ to take value $1$ when $x_t$ is positive is done with $x_t \le b_t$, assuming $x_t \le 1$.

For the second part, quoting @MarkL.Stone:

You will have to choose a tolerance as to how close to zero should be considered zero

Let $\epsilon$ be this tolerance. So you want to enforce $$ x_t < \epsilon\implies b_t = 0 $$

Now referring to this link (careful as $b$ in the link is a constant $\neq$ your $b_t$):

To enforce "if $x < b$ then $y=1$": $$b - x \le My,$$ where $M$ is a large constant. The logic is that if $b - x > 0$, then $y$ must equal 1, and otherwise it may equal 0.

Given that $x_t \le 1$, and that you want the binary variable to take value $0$ (and not $1$), the constraint becomes: $$ \epsilon-x_t \le 1-b_t $$

It is easy to see that if $b_t$ takes value $1$, then it implies $x_t \ge \epsilon$, which is the contrapositive of what you want.

$\endgroup$
3
  • $\begingroup$ Thanks Kuifje for your answer (I upvoted it). The shorter (and simpler) answer given by worldsmithhelper seems to work. I have implement it and not experienced any problems so far. Do you see any problems with that answer? $\endgroup$ – PeterBe May 20 at 10:10
  • 2
    $\begingroup$ Both approaches are similar and deal with a tolerance ($\epsilon$ or $1/m$), but the way the tolerance is handled is a bit different. $\endgroup$ – Kuifje May 20 at 10:18
  • $\begingroup$ I would say try both and reward the one giving you better performance in your problem. $\endgroup$ – worldsmithhelper May 20 at 10:22
0
$\begingroup$

Many solvers and APIs allow logical constraints.

For instance with OPL CPLEX you may write

dvar float+ x;
dvar boolean b;

subject to
{
  
  b==!(x==0);
}
$\endgroup$
3
  • $\begingroup$ Thanks for your answerAlex How can I formulate this with equations? I do not use OPL CPLEX and I would like to have an answer that is independent from the modelling language and the solver. $\endgroup$ – PeterBe May 18 at 9:05
  • $\begingroup$ Then see or.stackexchange.com/questions/33/… $\endgroup$ – Alex Fleischer May 18 at 9:44
  • $\begingroup$ Thanks for the link Alex. I think that the answer there does not quite answer my question. There it is stated for continous variables that there are 2 cases: Case 1 "if x>b then y=1" --> this also holds for my example and is in line with what I want. In my case b is just 0. However, the Case 2: "if x=b then y=1" is not in line with what I want. if x=b (and b is 0 in my case) then y should be also 0. Any idea how I can formulate this with equations? $\endgroup$ – PeterBe May 18 at 10:49

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.