# Exploiting structure in KKT system using JuMP

**URL:** <https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, linearalgebra\
**Created:** [October 16, 2017, 1:12am UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456 "2017-10-16T01:12:28Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 16, 2017, 1:12am UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/1 "2017-10-16T01:12:28Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![aleksip](https://avatars.discourse-cdn.com/v4/letter/a/cdc98d/32.png) [@aleksip](https://discourse.julialang.org/u/aleksip)\
**Post date:** [October 16, 2017, 7:57am UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/2 "2017-10-16T07:57:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 16, 2017, 5:14pm UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/3 "2017-10-16T17:14:55Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [October 16, 2017, 5:24pm UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/4 "2017-10-16T17:24:51Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 16, 2017, 5:39pm UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/5 "2017-10-16T17:39:13Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [October 16, 2017, 5:51pm UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/6 "2017-10-16T17:51:58Z")

</div>

Here are some benchmark results for various solvers: [Decison Tree for Optimization Software](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.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 16, 2017, 6:30pm UTC](https://discourse.julialang.org/t/exploiting-structure-in-kkt-system-using-jump/6456/7 "2017-10-16T18:30:16Z")

</div>

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.