6
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 6 at 13:42
  • $\begingroup$ 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. $\endgroup$
    – Clement
    Aug 6 at 16:43
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Clement
    Aug 6 at 17:49
  • $\begingroup$ 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). $\endgroup$ Aug 11 at 13:13
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If t=0 then delta can be 0 or 1, both are feasible. So this does not enforce P=1. $\endgroup$ Aug 6 at 8:31
  • $\begingroup$ Yes, we also have to enforce $t=0 \Rightarrow \delta = 1$. $\endgroup$
    – Kuifje
    Aug 6 at 8:34

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.