Math-opt gurobi: SafeGurobiDouble/GRB_INFINITY only checked for lhs/rhs, but not coefficients?

[sschnug]

What version of OR-Tools and what language are you using?
Version: main.
Language: C++

The gurobi-wrapper in math-opt has this helper:

absl::Status SafeGurobiDouble(const double d) {
  if (std::isfinite(d) && std::abs(d) >= GRB_INFINITY) {
    return util::InvalidArgumentErrorBuilder()
           << "finite value: " << d << " will be treated as infinite by Gurobi";
  }
  return absl::OkStatus();
}

It's used to guard against finite-but-out-of-range values like 1e123 while:

#define GRB_INFINITY 1e100

These checks ARE EXECUTED in:

• GurobiSolver::AddNewLinearConstraints
• GurobiSolver::AddNewQuadraticConstraints
• GurobiSolver::AddNewIndicatorConstraints

but are only applied to lhs/rhs.

These checks ARE NOT EXECUTED in:

• GurobiSolver::ChangeCoefficients

Now while i think gurobi-tests are not part of the public repository, there is gscip_solver_test.cc and this test:

TEST(GScipSolverTest, InvalidCoefficient) {
  Model model;
  const Variable x = model.AddVariable("x");
  model.Maximize(x);
  model.AddLinearConstraint(1.0e123 * x <= 2.0, "broken constraint");
  EXPECT_THAT(Solve(model, SolverType::kGscip),
              StatusIs(absl::StatusCode::kInvalidArgument,
                       HasSubstr("broken constraint")));
}

My claim: (which i can't check as i have no access to gurobi):

• The gurobi wrapper would fail for this test or problems with the same problematic coefficients

(might also be relevant for objective coefficients which i did not check)

[soppera]

First I tested with an additional test:

TEST(GurobiTest, UnsafeLinearConstraintCoefficient) {
  Model model;
  const Variable x = model.AddVariable("x");
  model.AddLinearConstraint(1.0e123 * x <= 2.0, "c");
  model.Maximize(x);

  ASSERT_OK_AND_ASSIGN(
      const SolveResult result,
      Solve(model, SolverType::kGurobi, {
                .message_callback=InfoLoggerMessageCallback("GUROBI > "),
        }));
  LOG(INFO) << result;
  ASSERT_THAT(result, IsOptimal(0.0));
  LOG(INFO) << "x value = "
            << RoundTripDoubleFormat(result.variable_values().at(x));
}

Running this test with Gurobi leads to:

[ RUN      ] GurobiTest.UnsafeLinearConstraintCoefficient
I] GUROBI > Gurobi Optimizer version 11.[…]
I] GUROBI > 
I] GUROBI > […]
I] GUROBI > 
I] GUROBI > Optimize a model with 1 rows, 1 columns and 1 nonzeros
I] GUROBI > Model fingerprint: 0xd7d3645a
I] GUROBI > Coefficient statistics:
I] GUROBI >   Matrix range     [1e+100, 1e+123]
I] GUROBI >   Objective range  [1e+00, 1e+00]
I] GUROBI >   Bounds range     [0e+00, 0e+00]
I] GUROBI >   RHS range        [2e+00, 2e+00]
I] GUROBI > Warning: Model contains large matrix coefficient range
I] GUROBI >          Consider reformulating model or setting NumericFocus parameter
I] GUROBI >          to avoid numerical issues.
I] GUROBI > Presolve removed 1 rows and 1 columns
I] GUROBI > Presolve time: 0.00s
I] GUROBI > Presolve: All rows and columns removed
I] GUROBI > Iteration    Objective       Primal Inf.    Dual Inf.      Time
I] GUROBI >        0   -0.0000000e+00   0.000000e+00   0.000000e+00      0s
I] GUROBI > 
I] GUROBI > Solved in 0 iterations and 0.00 seconds (0.00 work units)
I] GUROBI > Optimal objective -0.000000000e+00
I] GUROBI > 
I] GUROBI > User-callback calls 34, time in user-callback 0.00 sec
I] {termination: {reason: optimal, problem_status: {primal_status: feasible, dual_status: feasible, primal_or_dual_infeasible: false}, objective_bounds: {primal_bound: -0, dual_bound: -0}}, solve_stats: {solve_time: 6.699833ms, simplex_iterations: 0, barrier_iterations: 0, first_order_iterations: 0, node_count: 0}, solutions: [1 available], primal_rays: [], dual_rays: []}
I] x value = 0
[       OK ] GurobiTest.UnsafeLinearConstraintCoefficient (16 ms)

So Gurobi is “fine” with the incorrect coefficient. It only complains about the ranges.

[soppera]

The SafeGurobiDouble() function has been added for bounds as the GRB_INFINITY value is used to decide if a constraint is single-sided or double-sided, and which type of constraint this is (GRB_LESS_EQUAL, GRB_GREATER_EQUAL, GRB_EQUAL).

Gurobi treats specifically constraints RHS values that are outside range: https://docs.gurobi.com/projects/optimizer/en/current/reference/attributes/constraintlinear.html#rhs

So it makes sense to emit an error for values outside range. As illustrated by the previous comment this is not the case for coefficients. Thus we don't emit an error here.

[soppera]

Looking a bit more into it, after having noticed that https://docs.gurobi.com/projects/optimizer/en/current/reference/attributes/constraintlinear.html#rhs mentions 1e20 and not GRB_INFINITY for a guard value, I made these tests:

RHS < 1e20

  Model model;
  const Variable x = model.AddVariable("x");
  model.AddLinearConstraint(1.0e22 * x <= 1.0e19, "c");
  model.Maximize(x);

This solves as optimal with x = 1.000000000e-03.

RHS > 1e20

  Model model;
  const Variable x = model.AddVariable("x");
  model.AddLinearConstraint(1.0e22 * x <= 1.0e21, "c");
  model.Maximize(x);

This results in Infeasible or unbounded model.

Conclusions

1. big coefficients are OK-ish, hence it is OK to not use SafeGurobiDouble() for them in MathOpt in my opinion,
2. RHS is special and needs to be tested
3. but we should stop using GRB_INFINITY here and instead use 1e20 as the tests clearly illustrate that constraints which |RHS| ≥ 1e20 are ignored.

[soppera]

Some more tests with:

  Model model;
  const Variable x = model.AddVariable("x");
  // <see constraints below>
  model.Maximize(x);

• model.AddLinearConstraint(x <= 1.0e19, "c"); → x = 1e+19
• model.AddLinearConstraint(x <= 1.0e21, "c"); → Infeasible or unbounded model
  Expected result, the constraint is ignored as RHS > 1e20.
• model.AddLinearConstraint(1.0e21 <= x <= 1.0e21, "c"); → x = 1e+21
  Equality constraint, in that case Gurobi would accept a RHS > 1e20, but we may reject it for consistency.
• model.AddLinearConstraint(3 <= x <= 1.0e21, "c") → Infeasible or unbounded model
  Note here the Gurobi does not support dual bounded constraint. Hence this one is implemented by MathOpt using a slack variable which bounds are [3, 1e21] and an equality constraint.
  But it seems this still is considered an unbounded model.
• model.AddLinearConstraint(1.0e17 <= x <= 1.0e21, "c"); → Infeasible or unbounded model
• model.AddLinearConstraint(1.0e20 * x <= 1.0e30, "c"); → Infeasible or unbounded model
  Expected result, the constraint is ignored as RHS > 1e20, even with the coefficient of x that could easily be used for scaling the constraint back into a better range.
• model.AddLinearConstraint(1.0e10 <= 1.0e20 * x <= 1.0e30, "c"); → x = 1e-10
  Totally unexpected result. Here for some reason Gurobi uses the lower-bound (we still maximize on x here) to give x a value: x = lower_bound / coefficient = 1e10/1e20 = 1e-10.

Conclusion from these tests: all cases but equality constraints seems to have issue with bounds greater than 1e20. It is not really worth supporting the equality case at this point as a special case though.

[soppera]

Actually the variables bounds are also considered infinite when outside [-1e20, 1e20].

See:

• https://docs.gurobi.com/projects/optimizer/en/current/reference/attributes/variable.html#lb
• https://docs.gurobi.com/projects/optimizer/en/current/reference/attributes/variable.html#ub

Thus the behavior of dual bounded constraint that we implement with a slack variable is consistent.