8

When I mark a variable in a Gurobi MIP model as binary, sometimes Gurobi gives me a solution where that variable has a fractional value other than 0 or 1. How do I constraint a variable to be honest-to-goodness truly binary?

The Gurobi documentation says "integer variables will often take values that aren't exactly integral". Gurobi allows setting IntFeasTol to a lower value, but this doesn't always solve the issue. A staff member writes "in many models, rounding to an exact integer value can create problems, such as making the solution infeasible" but if the result is that the model is infeasible, I would rather know that, instead of being returned a value that isn't actually integer. Is there a way to do this in Gurobi?

Hexaly
  • 2,976
  • 1
  • 11
  • 17
D.W.
  • 230
  • 1
  • 10
  • 7
    You linked to 9.0 documentation. New in Gurobi 9.1, just released. https://www.gurobi.com/products/gurobi-optimizer/whats-new-current-release/ "The new features in the release include: ... Integrality Focus: This new feature allows users to be much stricter on integrality constraints, thus avoiding many undesirable results (including trickle flows) that can come from small integrality violations." – Mark L. Stone Nov 06 '20 at 23:55
  • 3
    Welcome to the world of floating point arithmetic! – mattmilten Nov 07 '20 at 10:24
  • 2
    A simple way to avoid such an issue for the users is that optimization solvers consider integer variables as integers in their API. Meaning that the type of the value of an integer variable is an integer (and not a floating-point number). Also meaning that the solver has to deal with numerical troubles, not the user (or as least as possible). This is the case of the LocalSolver API. No will to make publicity here; we modestly think that this idea could be of interest to developers of MILP solvers. – Hexaly Nov 09 '20 at 22:54

1 Answers1

10

Gurobi has apparently been listening to you and others with similar concerns. Gurobi 9.1 was just released and introduces a new parameter IntegralityFocus to somewhat ameliorate those concerns (although I haven't tried it yet, so don't know how well).

Gurobi 9.1 Reference Manual page for InetgralityFocus

Integrality focus
Type: int

Default value: 0

Minimum value: 0

Maximum value: 1

One unfortunate reality in MIP is that integer variables don't always take exact integral values. While this typically doesn't create significant problems, in some situations the side-effects can be quite undesirable. The best-known example is probably a trickle flow, where a continuous variable that is meant to be zero when an associated binary variable is zero instead takes a non-trivial value. More precisely, given a constraint $y \le M b$ where $y$ is a non-negative continuous variable, $b$ is a binary variable, and $M$ is a constant that captures the largest possible value of $y$, the constraint is intended to enforce the relationship that $y$ must be zero if $b$ is zero. With the default integer feasibility tolerance, the binary variable is allowed to take a value as large as $1e-5$ while still being considered as taking value zero. If the $M$ value is large, then the $M$ upper bound on the $y$ variable can be substantial.

Reducing the value of the IntFeasTol parameter can mitigate the effects of such trickle flows, but often at a significant cost, and often with limited success. The IntegralityFocus parameter provides a better alternative. Setting this parameter to 1 requests that the solver work harder to try to avoid solutions that exploit integrality tolerances. More precisely, the solver tries to find solutions that are still (nearly) feasible if all integer variables are rounded to exact integral values. We should say that the solver won't always succeed in finding such solutions, and that this setting introduces a modest performance penalty, but the setting will significantly reduce the frequency and magnitude of such violations.

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67