1
$\begingroup$

For a binary variable $y$ and another decision variable $x$, $x$ being integer, I want to be able to use the following two non-linear constraints into a linear solver:

\begin{align} x\ge 0 \implies y = 1\\ x< 0 \implies y = 0 \end{align}

What I've tried so far is:

$$\dfrac{x}{M} + \varepsilon \le y$$ $$\dfrac{x}{M}+1\ge y$$

With $M$ being a large constant and $\varepsilon$ a very small constant.

I then wanted to use those constraints in a linear programming solver and my problem is that whatever value of $M$ and $\varepsilon$, when $x = 0$, $y$ is always $0$ instead of $1$. All other cases are working. What mistake could have made? Is there another way without constants $M$ and $\varepsilon$?

$\endgroup$
  • $\begingroup$ How can you hope to linearize the step function well at its point of discontinuity? $\endgroup$ – madnessweasley Aug 27 '19 at 9:55
  • $\begingroup$ @madnessweasley, indeed linearize is not the exact word, what I want is to be able to use it in a linear solver taking advatange of the properties of my problem, $x$ is an integer, $y$ is binary :) $\endgroup$ – JKHA Aug 27 '19 at 10:41
  • $\begingroup$ So how large is your $M$? The name big-M is misleading, as you are supposed to pick it as small as possible, i.e., in theory you let it be arbitrarily large, but in practice with solver which work with finite tolerances, you have to select it carefully to avoid numerical problems. In this case, it should be the smallest possible upper bound on the optimal $x$. $\endgroup$ – Johan Löfberg Aug 27 '19 at 11:14
0
$\begingroup$

$$ \begin{align} x\ge 0 \implies y = 1\\ x< 0 \implies y = 0 \end{align} $$

I assume your variable $y\in \{0,1\}$ because there is no another possibility. Let $M$ be a big positive number.

$$ \begin{align} x \geq (y-1)M\\ x < yM\\ -M \leq x < M \end{align} $$

Using the intervals $[-M, 0), [0, M)$ this set of constraints guarantees the asked properties. OK, this is exactly what you do, but when $x=0$ the second constraint $0<yM$ then $y\neq 0$.

You can rewrite as follow ($\epsilon > 0$) :

$$ \begin{align} x \geq (y-1)M\\ x + \epsilon \leq yM\\ -M \leq x < M \end{align} $$

Note that $x + \epsilon \leq yM$ and $\frac{x}{M}+\epsilon \leq y$ are the same thing. It is correct. Probably, you make a mistake in your code because when $(x,y)=(0,0)$ the second constraint becomes $\epsilon \leq 0$. It is false for all $\epsilon >0$.

UPDATE

I think you proof these constraints using the following idea. Let $M>0$ be a big number and $\epsilon>0$ a small number. Assume $-M \leq x \leq M-\epsilon$.

$$y=\left\lfloor\frac{x}{M}\right\rfloor+1$$

Note that $0 \leq x \leq M-\epsilon \implies y=1$ and $-M \leq x < 0 \implies \lfloor\frac{x}{M}\rfloor = -1 \implies y=0$

$$y-1=\left\lfloor\frac{x}{M}\right\rfloor$$

$$y-1\leq \frac{x}{M} < y $$

$$y-1\leq \frac{x}{M} \leq y -\frac{\epsilon}{M}$$

$$ \left\{\begin{align} & x \geq (y-1)M\\ & x \leq yM -\epsilon \end{align}\right. $$

$\endgroup$

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.