Objective scaling leads to inconsistent gaps in B&B

[DanielHermosilla]

When running a problem with user_objective_scale, I believe that the expected behavior is to scale only the part of the objective associated with columns, leaving the offset untouched. However, the gaps used to determine B&B convergence are computed using the unscaled offset, leading to false gaps and inconsistent results. Note that relative gaps should be invariant to the offset. However, the way HiGHS currently calculates them is not invariant, since the common scaling factor does not cancel out.

In particular, let’s consider this toy instance. Solving it to optimality with the default options yields the following results:

Solving report
  Status            Optimal
  Primal bound      -671
  Dual bound        -671
  Gap               0% (tolerance: 0.01%)
  Nodes             1

However, if I set user_objective_scale to -10, it logs the following:

Solving report
  Model             repro
  Status            Optimal
  Primal bound      498.903320312
  Dual bound        498.853515625
  Gap               0.00998% (tolerance: 0.01%)

In theory, this should not be a problem, since HiGHS reports these values in the scaled space. However, the unscaled solution is inconsistent with the first result:

After solving the user-scaled model, the unscaled solution has objective value -623

As I mentioned before, this originates because the gap is internally calculated as

$$ \text{GAP}=\frac{s(P-D)}{\vert s\cdot P + \text{offset}(1-s)\vert}. $$

This was run with HiGHS 1.15.1, but, based on the commit history, the issue has been present since version 1.12.x.

⸻

The fix is quite simple. I do not fully understand how to open a pull request in this project; however, the required change is straightforward.

In the file HiGHS/highs/lp_data/HighsLpUtils.cpp, inside userScaleLp, add the following block:

if (apply)
    lp.offset_ *= std::pow(2, data.user_objective_scale) *
                  std::pow(2, data.user_bound_scale);

Then, in HiGHS/highs/lp_data/HighsInterface.cpp, replace this block:

// In scaling the objective function value, have to consider the offset
double objective_function_value =
    info_.objective_function_value - model_.lp_.offset_;
objective_function_value *= (bound_scale_value * objective_scale_value);
objective_function_value += model_.lp_.offset_;
info_.objective_function_value = objective_function_value;
// The MIP dual bound is another value in objective space, so apply exactly
// the same transform to it, so that it is reported in the original
// (unscaled) space too. Only meaningful for a MIP (integrality present).
if (has_integrality) {
  double mip_dual_bound = info_.mip_dual_bound - model_.lp_.offset_;
  mip_dual_bound *= (bound_scale_value * objective_scale_value);
  mip_dual_bound += model_.lp_.offset_;
  info_.mip_dual_bound = mip_dual_bound;
}

with this:

info_.objective_function_value *=
    (bound_scale_value * objective_scale_value);
// The MIP dual bound is another value in objective space, so unscale it in
// the same way, so that it is reported in the original space too.
if (has_integrality)
  info_.mip_dual_bound *= (bound_scale_value * objective_scale_value);

At this point, I would also suggest replicating the behavior of other solvers and logging the primal and dual bounds in the unscaled space, including the offset. I can provide the corresponding code if a PR is opened.

[jajhall]

Indeed, I'd overlooked the offset.

At the moment, I can't see myself logging the primal and dual bounds in the unscaled space. The "user scaling" is very much in the spirit of "this is what HiGHS would give you if you scaled your model in this way" - rather than an attempt to solve the original model.

[jajhall]

Closed by #3186