Slow presolve with "large" simple model

[jurasofish]

I have the model below which is very simple but somewhat "large" with 10_000 vars.
It takes 0.04 seconds with presolve off vs 0.7 with presolve on.
The ratio of times (0.7/0.04) seems to stay pretty constant as I increase the number of variables.

Is there any general guidance on how to have HiGHS automatically presolve or not as appropriate in a situation like this?

import time

import highspy
import numpy as np


def run(presolve: str, n_vars: int) -> None:
    t1 = time.perf_counter()
    h = highspy.Highs()

    lb = np.full(n_vars, 0.0, dtype=np.float64)
    ub = np.full(n_vars, 1.0, dtype=np.float64)
    h.addVars(n_vars, lb, ub)

    _ = h.changeColsCost(
        n_vars,
        np.arange(n_vars, dtype=np.int64),
        np.arange(n_vars, dtype=np.float64),
    )
    h.changeObjectiveSense(highspy.ObjSense.kMaximize)

    _ = h.addRows(
        1,
        np.array([1]),
        np.array([1]),
        n_vars,
        np.array([0]),
        np.arange(n_vars, dtype=np.float64),
        np.full(n_vars, 1, dtype=np.float64),
    )

    h.setOptionValue("log_to_console", True)
    h.setOptionValue("presolve", presolve)
    h.run()
    sol = h.getSolution()
    sol_value = sum(np.array(sol.col_value) * np.arange(n_vars, dtype=np.float64))
    assert np.isclose(sol_value, n_vars - 1)
    t2 = time.perf_counter()
    print(f"----> Time to solve with {presolve=}: {t2 - t1:.2f}s")


if __name__ == "__main__":
    assert highspy.Highs().version() == "1.5.3"
    n_vars = 100_000
    run("off", n_vars)
    print("\n")
    run("on", n_vars)

Output

Running HiGHS 1.5.3 [date: 2023-05-16, git hash: 594fa5a9d]
Copyright (c) 2023 HiGHS under MIT licence terms
Solving LP without presolve or with basis
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
          1     9.9990000000e+03 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 1
Objective value     :  9.9990000000e+03
HiGHS run time      :          0.04
----> Time to solve with presolve='off': 0.04s


Running HiGHS 1.5.3 [date: 2023-05-16, git hash: 594fa5a9d]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
1 rows, 10000 cols, 10000 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-1); columns 0(-10000); elements 0(-10000) - Reduced to empty
Solving the original LP from the solution after postsolve
Using EKK primal simplex solver
  Iteration        Objective     Infeasibilities num(sum)
          0     9.9865276977e+03 Pr: 0(0); Du: 9998(4.9985e+07) 0s
          1     9.9990000000e+03 Pr: 0(0) 0s
Model   status      : Optimal
Simplex   iterations: 1
Objective value     :  9.9990000000e+03
HiGHS run time      :          0.71
----> Time to solve with presolve='on': 0.71s

[jajhall]

Sorry not to have replied sooner, I've been away for a fortnight.

I'll check that I can reproduce your observations, but my instinct tells me that you've got a somewhat anomalous LP, since it has only one constraint that is fully dense. I can only think that there are some presolve actions performed repeatedly, each of which has a cost proportional to the number of nonzeros.

As a general rule, using presolve can be expected to be advantageous, and significantly so in many cases. Hence it's on by default. However, when large numbers of models of a particular type are to be solved, it's worth trying with and without presolve just to check.

[jajhall]

So, since each of your variables is identical in terms of its cost, bounds and contribution to the constraint, presolve eliminates them one-by-one once it's done an initial analysis of all the columns to identify that this is possible. This initial presolve overhead explains why it's more expensive to use presolve to reduce the LP to empty, than do the single simplex iteration required to solve the problem.

[ruffoh]

yes