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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .