Exploiting structure in KKT system using JuMP

jump
linearalgebra

#1

Suppose I have a LP in which objective and constraints only involve neighboring variables. That is, I have a matrix variable X and each of my expressions only involve the variables X[i,j], X[i-1,j], X[i+1,j], X[i,j-1], X[i,j+1]. This setup leads to a banded KKT system that can be solved much more efficiently (no need to invert a full matrix).

Will JuMP (and the optimization solvers behind it) automatically detect the banded matrix and call specialized linear solvers that exploit this structure?

As a side question, is there any way to query the size of a JuMP problem (number of variables, constraints, etc.) after it is setup?


#2

About you side question, you get a short summary of your optimization problem using show(modelName), or simply writing modelName in the REPL. In the Methods section of http://jump.readthedocs.io/en/latest/refmodel.html you can see quite a few methods to find out various aspects of the problem (number of variables etc.).


#3

Thank you @aleksip, good to know about these methods.

Regarding the main question, I have a JuMP model with 30000 variables and 103500 linear constraints. It is being solved in about 18s, which seems like a lot.

I just want to confirm that JuMP (and solvers) are smart about the banded matrix, otherwise I will have to implement an efficient Newton update myself for maximum performance?


#4

Since JuMP requires you to explicitly choose your solver, it can’t choose a solver for you based on the particular structure of your matrix. So I think that it would be the solver’s responsibility to take advantage of that structure. What LP solver are you using?


#5

Thank you @rdeits, I am using ECOS, but I don’t have a good justification for it, just picked a solver at random based on previous experience. Is there a benchmark table somewhere where I can see the advantages/disadvantages of each solver?

I agree that this performance boost is something that regards the solvers, but I wonder if JuMP has some explicit language to force this type of code optimization or if it is passing the appropriate format to the underlying solver?


#6

Here are some benchmark results for various solvers: http://plato.la.asu.edu/bench.html. A fair number of these solvers is also available through JuMP. ECOS isn’t included in the benchmarks though.


#7

Thank you @tkoolen, any plans to create a benchmark package for JuMP solvers? A simple package with a set of JuMP models and data, and a function to run the models and print the output in a table format.