Add min-fill ordering.

[samuelsonric]

You are currently using the AMD algorithm to compute elimination orderings (as part of your clique tree machinery). AMD is a great linear-time algorithm, but there are quadratic-time algorithms that compute orderings with less fill. This PR replaces AMD with the minimum-local-fill algorithm. On some problems, the difference in solve time is dramatic.

julia> using Clarabel, ClarabelBenchmarks

AMD

julia> ClarabelBenchmarks.PROBLEMS["sdplib"]["arch0"](Clarabel.Optimizer);
-------------------------------------------------------------
           Clarabel.jl v0.10.0  -  Clever Acronym              

                   (c) Paul Goulart                          
                University of Oxford, 2022                   
-------------------------------------------------------------
[...]
Terminated with status = solved
solve time =  21.8s

Minimum-Local-Fill

julia> ClarabelBenchmarks.PROBLEMS["sdplib"]["arch0"](Clarabel.Optimizer);
-------------------------------------------------------------
           Clarabel.jl v0.10.0  -  Clever Acronym              

                   (c) Paul Goulart                          
                University of Oxford, 2022                   
-------------------------------------------------------------
[...]
Terminated with status = solved
solve time =  3.06s

I omitted the greater part of the printout.

[CLAassistant]

All committers have signed the CLA.

[samuelsonric]

This should probably be toggled by a setting.

[goulart-paul]

Thank you for this suggestion, which looks very interesting. Two questions here:

1. You used the alternative ordering in the clique identification step for chordal decomposition, but don't suggest using the alternative ordering method for the KKT factorisation itself. I tried that myself and it seems that while the min-fill ordering has a very large positive effect on the chordal decomposition, it makes things somewhat worse for the factorisation. I only tried that on the one problem you pointed out though -- not sure if it holds generally.

Do you have some idea what is going on here? Is the min-fill ordering in some way advantageous for chordal decomposition specifically? If so, I guess it would make sense to allow a choice or ordering methods for the chordal decomposition independently of the KKT factorisation. Perhaps that's preferable anyway, since some linear solvers (e.g. MKL) use their own orderings anyway.

2. Can you give a sense of how much of an effort it would be to port the min-fill ordering (and maybe other relevant methods from CliqueTrees.jl) to rust?

[samuelsonric]

1. Would you mind showing me how you inserted the MF ordering into the kkt factorization routine? Or push your branch?

2. A port should be very easy. The algorithm is implemented here in 182 lines. It depends on the Graph type from Graphs.jl and a Heap type defined in this file. The weights vector is a vector of nonnegative vertex weights; in your case, they would all be set to 1.

[goulart-paul]

1. Would you mind showing me how you inserted the MF ordering into the kkt factorization routine? Or push your branch?

See here: https://github.com/oxfordcontrol/Clarabel.jl/tree/pg/pr199

All that is required is to provide an ordering for the main kkt solver in exactly the way you did within the chordal decomposition code. In the branch above it's just a one-line change, although it would only work when using the :qdldl KKT factorisation method. It probably would also want to be a configurable option, but I think sufficient to try it out if you are interested.

[samuelsonric]

Following up on 2.

AMD(; dense=15.0) is finding less fill than MF() for the KKT matrix (1.2M vs 1.4M nonzeros). The MF generally performs better than AMD, but not always. The KKT matrix is also much bigger than the constraint matrix, so the cost to run MF is nonnegligible (~1s).

The current implementation of MF is frankly much slower than it should be; before the end of the year I plan to replace it with a substantially faster one.

[samuelsonric]

@goulart-paul Incidentally, I am working on a generic tool for performing the decomposition.

https://github.com/samuelsonric/MathOptChordalDecomposition.jl