added optimal_coloring

[dstahlke]

Use PicoSAT to find the optimal proper coloring of a graph.

[codecov-commenter]

Codecov Report

Patch coverage: 93.93% and project coverage change: -1.30% :warning:

Comparison is base (8a43175) 98.94% compared to head (72d4652) 97.65%.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #12 +/- ## ========================================== - Coverage 98.94% 97.65% -1.30% ========================================== Files 5 6 +1 Lines 95 128 +33 ========================================== + Hits 94 125 +31 - Misses 1 3 +2 ``` | [Files Changed](https://app.codecov.io/gh/gdalle/GraphsOptim.jl/pull/12?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Guillaume+Dalle) | Coverage Δ | | |---|---|---| | [src/GraphsOptim.jl](https://app.codecov.io/gh/gdalle/GraphsOptim.jl/pull/12?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Guillaume+Dalle#diff-c3JjL0dyYXBoc09wdGltLmps) | `100.00% <ø> (ø)` | | | [src/coloring.jl](https://app.codecov.io/gh/gdalle/GraphsOptim.jl/pull/12?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Guillaume+Dalle#diff-c3JjL2NvbG9yaW5nLmps) | `93.93% <93.93%> (ø)` | |

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[gdalle]

Hey! I have seen the PR and I'm grateful for the contribution, but I don't have time to review rn, hopefully in the coming weeks. Do you need this urgently?

[dstahlke]

No hurry. Take your time.

[gdalle]

@dstahlke coming back to your PR now.

The immediate goal of this package is to leverage the JuMP ecosystem and remain solver-agnostic. Do you think you might be able to translate your implementation into a JuMP formalism instead of PicoSAT?

I think JuMP is starting to support constraint programming but I don't know how far they've come https://jump.dev/blog/constraint-programming-update/

[dstahlke]

It look like ConstraintProgrammingExtensions.jl is not compatible with GraphsOptim.jl. They have conflicting version requirements for MathOptInterface.

[gdalle]

Then I suggest we formulate this as an integer program

[dstahlke]

My concern with this is that it seems unusably slow. For example queens_graph(6) takes 16.5 seconds with ILP, as compared to 0.00276 seconds with PicoSAT. I'd imagine queens_graph(7) or queens_graph(8) would be out of reach with ILP.

[gdalle]

Good point. I will look into constraint programming in JuMP, it would be cool to have example of that too

https://discourse.julialang.org/t/status-of-constraint-programming-in-jump/105580