11
$\begingroup$

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.

$\endgroup$
  • 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$ – Discrete lizard Jun 17 '19 at 14:56
  • $\begingroup$ What is a CAS ? $\endgroup$ – LarrySnyder610 Jun 24 '19 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$ – Discrete lizard Jun 24 '19 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.