Solver acceleration

[dfridovi]

Currently, per #21 the IP solver is about 5x slower than PATH on random sparse QPs. It would be great to get it at least on par.

[lassepe]

I got a solid speedup from switching to a Krylov linear solver; see #24

I didn't do any larger-scale benchmark yet though since the benchmark/ stuff compiles forever on my machine.

[lassepe]

SymbolicTracingUtils.jl now supports generating lazy Jacobians that behave like a matrix (one can multiply them with A * x or mul!(result, A, x) ) but that don't allocate. These are supported by the LinearSolve.jl and thus we should be able to make the hot loop entirely matrix-free (while keeping the readable look-and-feel of matrices).

See: JuliaGameTheoreticPlanning/SymbolicTracingUtils.jl#2

[dfridovi]

Niiiiice let’s do it!

[dfridovi]

Btw if you want to try the benchmark stuff you can change the number of primals and constraints as keyword args in the benchmark() function. I’ll definitely also run it when I’m back at a computer next week.

[lassepe]

Can you elaborate how you concluded from the benchmarks that PATH is 5x faster? When I run the benchmarks as

data = SolverBenchmarks.benchmark()
SolverBenchmarks.summary_statistics(data)

I get:

(ip = (success_rate = 0.995, μ = 0.08008527012261307, σ = 0.01090576568028957), path = (success_rate = 0.0, μ = NaN, σ = NaN))

Which suggests that PATH is never able to solve the problem. Am I calling the wrong function? Maybe you could add a little README to the benchmark/ directory to clarify how to use it.

[dfridovi]

That is the right way to run the benchmarks... I am surprised that PATH is never solving correctly though. The two solvers have always matched which problems they solved in past trials I've run. I think we need to dig into these failures.

The README is a great suggestion - check #31

[dfridovi]

Btw did you possibly try it on a machine where you haven't set the PATH license string? Not sure what else would have changed since it's just calling the solver through ParametricMCPs and I haven't seen breaking changes there.

[dfridovi]

Back at a computer now. When I run the benchmarks on latest main I get this:

julia> SolverBenchmarks.summary_statistics(data)
(ip = (success_rate = 0.995, μ = 0.0929011982472362, σ = 0.011743631979417222), path = (success_rate = 0.995, μ = 0.007233340777889448, σ = 0.0012165875739682118))

i.e., we are now about 10x slower than PATH... (and PATH solves all the same problems we do). Will do some digging to see if I can speed things up by adjusting the Krylov solver settings.

[lassepe]

Btw did you possibly try it on a machine where you haven't set the PATH license string? Not sure what else would have changed since it's just calling the solver through ParametricMCPs and I haven't seen breaking changes there.

You are absolutely right. I just goofed up the license … 🙈

[lassepe]

i.e., we are now about 10x slower than PATH... (and PATH solves all the same problems we do). Will do some digging to see if I can speed things up by adjusting the Krylov solver settings.

The Krylov solver should benefit a lot from the lazy/matrix-free Jacobian representations in #26 . Now that I know how to do the benchmarks properly, I can check that

[dfridovi]

Btw I also realized this wasn't quite apples to apples since I never made the default IP solver tolerance match PATH. I'm working on #32 and including that. Your comment above is 100% correct though - I bet Krylov will be much better after #26 lands.

[dfridovi]

Ok messing with tolerances for Krylov isn't helping. I think we need #26 to land before doing more. On smaller problems now I am seeing IP is only about 2x worse than PATH, so that's nice.

[lassepe]

I wonder whether there is some structure to the randomly generated problems that makes an active-set approach more suitable. It may be worth also benchmarking on the MPGP example

[dfridovi]

That is fair.. I was wondering that as well.

[dfridovi]

#33 adds a trajectory game benchmark. It’s not doing anything fancy for initialization or receding horizon calls, but it’s a start. Currently it’s showing us waaaay slower than PATH.

[dfridovi]

I'll close this for now. #35 makes us 10x faster than PATH!