# Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?

It turns out that extending MILP with any of the constraints $$y=\lfloor x\rfloor$$, $$y=\lceil x\rceil$$, $$0 < x$$, or $$x\notin \mathbb{Z}$$ is 'equally hard'. (see my answer here, and below)

Expressing strict inequalities exactly in MILP is something that is generally considered not to be possible with standard solvers in practice without relying on finite precision of the solver, which can be tricky. (It is of course possible to deal with infinite precision reals algebraically with, e.g., a CAS, but this is much slower than inexact MILP solvers.)

The situation here is similar to that of complexity classes in complexity theory (and other applications of reductions within CS), where problems are shown to be 'equally hard' via reductions, but here we are not directly relating complexity.

Has this observation made before? Have equivalence classes under expressibility of 'common extensions' to exact MILP such as indicator constraints1 been studied? Are these classes known under another name?

To see why expressing these non-integrality constraints are equally 'hard' within MILP , note

• $$0 < x$$ can be expressed as $$0\leq x \wedge x\notin \mathbb{Z}$$ (or $$1-\lceil x\rceil + \lfloor x\rfloor \leq x$$)
• $$x\notin \mathbb{Z}$$ if and only if $$\lceil x\rceil - \lfloor x\rfloor = 1$$, which is $$0$$ otherwise.
• $$y=\lfloor x\rfloor$$ can be expressed as $$x-1 < y\leq x$$ with $$y\in\mathbb{Z}$$
• $$y=\lceil x\rceil = -\lfloor -x\rfloor$$

1: Big-M can be used in some cases, but only if variables are bounded, which is an assumption that makes the expressibility of this method weaker than indicator constraints both in theory and in practice. Of course, indicator constraints are usually slower to solve as a result.

• I'm not too happy with the name exact-reals, but I couldn't think of anything better for a tag about "expressing exact constraints over real numbers", which I think would useful. Commented Jun 17, 2019 at 14:56
• What is a CAS ? Commented Jun 24, 2019 at 2:40
• @LarrySnyder610 A computer algebra system. Mathematica, Maple and Sagemath are some examples. I added a link in the question. Commented Jun 24, 2019 at 6:22

Strict positivity, $$x > 0$$, is equivalent to the existence of nonnegative variable, $$r \geq 0$$, such that $$xr \geq 1$$. This means that it can be represented in second-order cone programming by the conic quadratic constraint $$x+r \geq \sqrt{ (x-r)^2 + 1^2 }.$$
Beware, however, that the given construction has two computational issues. Firstly, in finite precision arithmetic, the constraint $$x+r \geq \sqrt{ (x-r)^2 + 1^2 }$$ can be always be satisfied within tolerances by letting $$r$$ tend towards infinity and therefore does not exclude $$x=0$$. Secondly, the existences of a primal feasible ray $$(\bar x, \bar r)=(0,1)$$ that does not change the objective value, is equivalent to the existence of a dual facial reduction certificate. This means that constraint qualification fails for this construction as discussed in the paper Constraint qualification failure in action by Hijazi and Liberti.