Incremental solve with Glop is almost as slow as solving from scratch (?)

[ktp-max]

Hi all,

The short story:

I am using Glop through the MPSolver API in C++, OR-Tools 9.6. My task is solving a series of incremental LPs: before each subsequent run, I add to the model a few constraints and variables, and change some coefficients. Then I re-solve. This incremental process is repeated up to 30-40 times. However, except the first run which is super fast, the subsequent runs are almost as slow as solving the augmented model from scratch.

This comes in contrast to other solvers like HiGHs: when I solve exactly the same sequence of problems with HiGHs, the first run is about 50x slower than the corresponding run with Glop. But the next runs are what one could expect: each subsequent run takes only a fraction of the time of the first run. Eventually the total runtime among all sequential runs is 2-3X faster with HiGHS than with Glop. Same pattern when using Clp.

The details:

My problem is quite sparse i.e. each constraint has max 20 non-zeros. This is the case for all constraints except one major constraint which is very large. With every successive run, I add approximatelly 10% more small constraints and variables, and I add as many non-zeros to my major constraint. The interface I use for adding constraints/variables and modifying coefficients is the same as in the simplest OR-tools example online:

Variables are added individually with: MPSolver::MakeNumVar
Constraints are added individually with: MPSolver::MakeRowConstraint and the non-zeros in each constraint with MPConstraint::SetCoefficient.

I have set use_dual_simplex as the algorithm used. After each time I add a batch of new data, I run MPSolver::Solve with no further options.

My main concern is that in every run, even after the initial run, presolve is called, then there is a "Dual feasibility" phase, and then a "Dual optimization" phase. I wonder if there is an option that I can set in order to avoid presolve and the dual feasibility phase. As an experiment, I checked what would happen if, before every new run, I deleted the solver and build/solve from scratch. The difference in runtime/iterations was small: runtime was pretty much the same, iterations increased only by 20% when solving from scratch.

Please let me know if there is any option that I can use to improve the performance of the incremental solve.

Thanks!

[lperron]

Glop used through the linear_solver or model_builder does not support any incrementalism.

It is support from what I saw in math_opt.

[rma350]

When you are using GLOP and want incrementalism, you should typically:

1. disable presolve (both on the original solve and the incremental solve). When presolve is enabled, if your presolved problem ends up with a slightly different structure, the basis is fixed up correctly and you lose the advanced start.
2. set the simplex method (primal or dual) manually (generally primal simplex is better if your change preserves primal feasibility, and dual simplex is better if your modification preserves dual feasibility, as in both cases you can skip phase one, but this is not true 100% of the time)
3. (Optional) consider disabling scaling, if your problem is already well scaled, this will get you a small performance boost.

Not all solvers require (1), e.g. Gurobi, although you still may want to try tweaking this for a little extra performance.

I think that if you disable presolve, I think you may be able to get an incremental solve with GLOP + MPSolver (this is not what lperron said). This does not look like it from linear_solver/glop_interface.cc, but incremental changes are detected inside of glop. Perhaps I am wrong, I would just try it.

Big picture, if you want incremental solves with or-tools, you should try to use mathopt if you can instead of mpsolver, there is better support for it. Note that MathOpt + Highs does not yet support incrementalism, we just have not taken the time to do this.

[ktp-max]

@lperron @rma350

Thanks for both of the answers, I will try both approaches. How can I disable presolve? Is there an option in the MPSolver interface that can do that?

[ktp-max]

I found the interface in the MPSolver, it even has an incrementality option available! I tried it on a small dataset and I see that the number of iterations (and runtime) on the first solve increases quite a bit compared to the default version (presolve=on). But indeed the subsequent runs are much faster. Is there a way to avoid the runtime increase in the first run, so as to keep the best of both worlds? I will try it also on larger data to see if this pattern holds.

I will also try the mathopt interface, although there it is challenging to get the C++ API right. Do you think the runtime with mathopt will be substantially different?

[rma350]

With GLOP, you cannot have presolve on for the first solve and have incrementalism. In many cases, if your problem is much faster with presolve on, it is because you are intrdoucing many variables/cosntraints that can be eliminated by presolve (e.g. a variable with upper and lower bound of one). If you can just avoid creating these variables to begin with (a burden on your code), then you won't miss presolve as much. Or you can simply use a different LP solver. GLOP is just missing this feature.

For most C++ users, there is not much of a performance difference between mpsolver and mathopt, as the large majority of time is spent in the underlying solver. For users who are doing fast incremental solves, the overhead of both APIs is more visible. They each have their own advantages and disadvantages on performance due to using different algorithmic strategies, but usually it just doesn't matter. The real advantage of mathopt is better type safety and a larger feature set.

[ktp-max]

@rma350

Thanks again for providing all these details. I have not been able yet to run with the math-opt API (installation issues with v9.6), but here is a breakdown of runtime, iterations and presolve-related quantities on a toy dataset with approx 15 incremental runs:

First four columns are from Glop with presolve: runtime, iterations, initial number of rows, rows after presolve.
Next two columns are runtime and iterations of Glop without presolve, and final column is highs runtime.

One thing that strikes me is that presolve is doing an amazing job in the first run in removing constraints, but then it removes less constraints in the rest of the runs, despite the fact that the subsequent constraint sets are super-sets of the initial one. Is that expected?

Regarding again the amazing initial run, I wonder if I can identify the non-redundant constraints after presolve. One idea, of course would be to identify the active/critical constraints that define the optimal solution of the 1st run, but maybe something simpler can be available from the MpSolver interface? Like, run just presolve, and keep only the non-redundant rows? Given that, I am seeing the potential of using two solvers: one using Glop, which is dedicated to presolving and removing redundancies, and a second one using Highs which is fed the non-redundant ones from the first solver.

Also, would it help if I provide a hint solution to Glop+presolve?