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.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 17, 2019 at 14:56
  • $\begingroup$ What is a CAS ? $\endgroup$ Commented Jun 24, 2019 at 2:40
  • 1
    $\begingroup$ @LarrySnyder610 A computer algebra system. Mathematica, Maple and Sagemath are some examples. I added a link in the question. $\endgroup$ Commented Jun 24, 2019 at 6:22

1 Answer 1


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

To see this, just square both sides of the inequality and expand. Conclusively, MISOCP (mixed-integer second-order cone programming) is the complexity class you are looking for, extending MILP with all the constraints you list. There is quite a lot of material on MISOCP representability, but I don't recall having seen any of the constraints you list except strict positivity. Good references for this direction of research are Lectures on modern convex optimization: Analysis, algorithms, and engineering applications by Ben-tal and Nemirovski, and Mixed-integer convex representability by Lubin, Zadik and Vielma.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.