Presolve appears to prevent feasible incumbents being reconstructed, leading to massive search tree growth

[Gbtank]

Hi HiGHS Team,

I'm seeing a significant behavioural difference between solving a binary MIP with presolve enabled vs disabled.

I am running this through the C# HiGHS.Native 1.15.1 interface but have also tested the attached MPS file with a local HiGHS exe built from the main branch.

With presolve enabled:

• HiGHS repeatedly reports:

WARNING: Solution with objective ... has untransformed violations:
bound = 0;
integrality = 0;
row = 1

• No feasible incumbent is ever accepted.
• BestSol remains inf.
• The branch-and-bound tree grows rapidly (>100k nodes).
• The solve eventually times out or is OOM-killed.

With presolve disabled:

• No untransformed violation warnings occur.
• Feasible incumbents are found immediately.
• The model solves to optimality in ~14 seconds.
• Only 32 nodes are explored.

Attached to this issue you will find

• Problem-causing "model.mps" (uploaded as "model.txt")
• Results expected with presolve on "solver-log-presolve-on.txt"
• Results expected with presolve off "solver-log-pesolve-off.txt"

Side note, you will notice that our solver logs start by spamming:

"Rows:           1 upper bounds greater than or equal to        1e+20 are treated as +Infinity"

This is because we set NULLs to HiGHS infinite_bound option. Is this the right way of setting up an upper bound or should we be using Highs Infinity?

Many thanks,

Gbtank

---

solver-log-presolve-on.txt

model.txt

solver-log-presolve-off.txt

[jajhall]

Side note, you will notice that our solver logs start by spamming:

"Rows: 1 upper bounds greater than or equal to 1e+20 are treated as +Infinity"

This is because we set NULLs to HiGHS infinite_bound option. Is this the right way of setting up an upper bound or should we be using Highs Infinity?

Starting with the easy issue. I'm not a C# programmer, and I don't know what happens to the value NULLs when you pass it as a value for the infinite_bound option. It may well be that it's rejected as not being in the range [1e15, infinity). However, the point of the infinite_bound option is that it's the threshold for a bound being treated as infinity.

I appreciate that if you've set all your "infinite" bounds to 1e+20, you're getting a lot of "spam". This really ought to be presented as a summary of how many bounds are treated as infinity.

[jajhall]

I also note that you have costs in the range [6e+02, 7e+08]. These (as HiGHS warns) are excessive and, as HiGHS suggests, should be scaled down by 1e-3. The instance (without presolve) solves a bit faster with this objective scaling.

[jajhall]

Otherwise, the issue relating to WARNING: Solution with objective ... has untransformed violations: is interesting, and I'll look at it shortly

@Opt-Mucca / @fwesselm: I have a feeling that this is a postsolve error as it's O(1) and only affects one row

[Opt-Mucca]

@jajhall it looks like it's either a postsolve error or there's an incorrect presolve reduction

[Gbtank]

Starting with the easy issue. I'm not a C# programmer, and I don't know what happens to the value NULLs when you pass it as a value for the infinite_bound option. It may well be that it's rejected as not being in the range [1e15, infinity). However, the point of the infinite_bound option is that it's the threshold for a bound being treated as infinity.

Sorry for the confusion, what I mean to say is that we have a function like so (excuse the pseudocode):

void addBound(std::vector<int> indices, double? lower, double? upper) {
    auto solver = this.getInstance();

    // If lower == NULL, set to -solver.getInfiniteBound()
    double lowerBound = (lower == NULL)
        ? -solver.getInfiniteBound()  // should we be using -HighsInfinity here?
        : lower.value();

    // If upper == NULL, set to solver.getInfiniteBound()
    double upperBound = (upper == NULL)
        ? solver.getInfiniteBound() // should we be using +HighsInfinity here?
        : upper.value();

    // Use lowerBound and upperBound when adding the constraint
    // ...
}

As the comments ask, should we be setting to HighsInfinity instead of the infinite bound? I assume there is no difference internally as we see in the logs these are treated as infinity anyways.

[Gbtank]

I also note that you have costs in the range [6e+02, 7e+08]. These (as HiGHS warns) are excessive and, as HiGHS suggests, should be scaled down by 1e-3. The instance (without presolve) solves a bit faster with this objective scaling.

As far as I know there is no automated way to allow HiGHS to rescale your problem for you, is there?

[jajhall]

I also note that you have costs in the range [6e+02, 7e+08]. These (as HiGHS warns) are excessive and, as HiGHS suggests, should be scaled down by 1e-3. The instance (without presolve) solves a bit faster with this objective scaling.

As far as I know there is no automated way to allow HiGHS to rescale your problem for you, is there?

Scaling of the costs is achieved by setting a nonzero value of the option user_objective_scale. This is an integer to give power-of-two scaling, which is why HiGHS recommends

Consider scaling the objective by 1e-3, or setting the user_objective_scale option to -10

All the bounds on (continuous) variables and constraints can be scaled by setting the user_bound_scale option, but your bounds are OK

[Gbtank]

Scaling of the costs is achieved by setting a nonzero value of the option user_objective_scale. This is an integer to give power-of-two scaling, which is why HiGHS recommends

Consider scaling the objective by 1e-3, or setting the user_objective_scale option to -10

This requires us to run HiGHS, read the solver log, stop HiGHS, update the option and then run it again right? Is there any way to automate this process and let the solver automatically rescale the objective to what it thinks is best and will solve fastest without user input?

[jajhall]

Starting with the easy issue. I'm not a C# programmer, and I don't know what happens to the value NULLs when you pass it as a value for the infinite_bound option. It may well be that it's rejected as not being in the range [1e15, infinity). However, the point of the infinite_bound option is that it's the threshold for a bound being treated as infinity.

Sorry for the confusion, what I mean to say is that we have a function like so (excuse the pseudocode):

void addBound(std::vector indices, double? lower, double? upper) {
auto solver = this.getInstance();

// If lower == NULL, set to -solver.getInfiniteBound()
double lowerBound = (lower == NULL)
    ? -solver.getInfiniteBound()  // should we be using -HighsInfinity here?
    : lower.value();

// If upper == NULL, set to solver.getInfiniteBound()
double upperBound = (upper == NULL)
    ? solver.getInfiniteBound() // should we be using +HighsInfinity here?
    : upper.value();

// Use lowerBound and upperBound when adding the constraint
// ...

}

As the comments ask, should we be setting to HighsInfinity instead of the infinite bound? I assume there is no difference internally as we see in the logs these are treated as infinity anyways.

I'm puzzled. There's no getInfiniteBound() in HiGHS.

However, in the C# API, there is getInfinity(). This is the way to set bounds to infinity so you're not spammed by the logging when they are changed to infinity from 1e20.

[jajhall]

Scaling of the costs is achieved by setting a nonzero value of the option user_objective_scale. This is an integer to give power-of-two scaling, which is why HiGHS recommends

Consider scaling the objective by 1e-3, or setting the user_objective_scale option to -10

This requires us to run HiGHS, read the solver log, stop HiGHS, update the option and then run it again right? Is there any way to automate this process and let the solver automatically rescale the objective to what it thinks is best and will solve fastest without user input?

Indeed, you have to do this. However, many modellers naturally have costs of the same order of magnitude, so can predict what scaling is required.

In you case, you have the costs - since you provide them to HiGHS - so you can find the smallest cost (in absolute value) and set user_objective_scale so a factor 2^user_objective_scale maps this cost to 1.0 (approximately).

[jajhall]

@jajhall it looks like it's either a postsolve error or there's an incorrect presolve reduction

We've got an example from a client that is also showing significant untransformed violations. I switched off the more recent presolve reductions, but the error persists. Indeed, it's exposed by v1.13.0.

We need to be able to identify what reduction is responsible

[jajhall]

@fwesselm: the "enumerateSolutions" rule appears to be the source of the error.

Setting presolve_reduction_limit=2194, the error is still seen, but not if presolve_reduction_limit=2193. Reduction 2193 comes just before calling HPresolve::enumerateSolutions and this generates reduction 2194.

Also, with presolve_rule_off = 65536 (ie enumerateSolutions off) the MIP is solved easily without any report of untransformed violations.

[fwesselm]

@jajhall, @Opt-Mucca, I will have a look shortly.