Exploiting structure in KKT system using JuMP

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?

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.).

1 Like

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?

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?

1 Like

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?

Here are some benchmark results for various solvers: Decison Tree for Optimization Software. A fair number of these solvers is also available through JuMP. ECOS isn’t included in the benchmarks though.

1 Like

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.

1 Like