6

I am trying to model $t \leq 0.0 \implies P = 1.0$ else $P=1$ or $P=0$ where $0 \leq t \leq H$ is a bounded nonnegative real, and $P$ is binary.

I can use the expression $t + \epsilon P \ge \epsilon$ which however does not do the job when $0 < t < \epsilon$, since then it forbids $P=0$ (both $P=1$ and $P=0$ should be feasible in this case).

Is there a way to fix this problem? Is there a way to use tolerance settings of a solver to overcome this difficulty?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Clement
  • 2,252
  • 7
  • 13
  • 1
    I'll often (well, actually always) keep the ambiguity at the breakpoint, so the solver can pick the best solution there. I don't want to miss the opportunity to find a better solution just because of some silly epsilon that has no real practical meaning anyway. – Erwin Kalvelagen Aug 06 '21 at 13:42
  • Actually, whenever I try to work with epsilons, I run into trouble. Most of the time I get infeasibility, so the epsilon containing constraint proves of no use. In other cases, the solver declares a non-optimal solution to optimal. I was hopping that this is me doing wrong things, but it seems there is an issue with the epsilons when it comes to computer implementation. – Clement Aug 06 '21 at 16:43

2 Answers2

4

Your constraint is equivalent to "if P=0 then t>0" which involves strict inequality. Strict inequality is not something that can be handled by a MIP solver without using some sort of epsilon.

But can t actually be arbitrarily small but non-zero in your case? Maybe it is possible/acceptable to find a small enough epsilon to model your constraint so that it works in practice.

Daniel Junglas
  • 448
  • 3
  • 6
  • The behavior of the solver becomes unpredictable with different epsilons. With e <= 1E-6 the problem becomes infeasible. With e=0.0000009 the optimal solution is claimed to be 0.0. With e=1E-7 the solution is claimed to be 1406.27, which again is not the real optimum. The feasibilty tolerance is set to the value 1.0E-6. So e <= feasibilty tolerance leads to infeasibility and e > feasibility tolerance to wrong results. Is there a rule how to choose e in relation to the feasibility tolerance? The solver is cplex. – Clement Aug 06 '21 at 17:49
  • I don't think there is a rule of thumb, but having epsilons smaller than the tolerances is for sure asking for trouble. I cannot speak to the specifics of CPLEX (anymore). – Daniel Junglas Aug 11 '21 at 13:13
2

You could define a binary variable $\delta \in \{0,1\}$ that takes value $1$ if and only if $t=0$: \begin{align*} 0\le t &\le H(1-\delta) \\ 1-\delta &\le M t \end{align*} Then, enforce $$ \delta \le P $$

Note that choosing the right value for $M$ may be as tricky as finding the right $\epsilon$. You need $M$ big enough such that if $t=\epsilon$, $M\epsilon \ge 1$, so that $\delta$ can take value $0$ without violating the constraint.

Kuifje
  • 13,324
  • 1
  • 23
  • 56