GSoC 2023: Enhanced optimization solver interfaces for Sage

[Carlxuzhl]

This is a meta-ticket for the 2023 Google Summer of Code project.

We work on the following tasks and issues extracted from the Meta-ticket #26511:

MILP: Add CyLP backend #19219 Add MILP solver backends for HiGHS via scipy.optimize.linprog #32282 Meta-ticket: CVXPY integration #33920 Move sage optimization backend framework (sage.numerical.backends) to separate Cython packages #28920 Meta-ticket: Improvements to MixedIntegerLinearProgram, its backends, and InteractiveLinearProgram #20302 (This Meta-ticket consists of a bunch of open issues so we will further look close into it and decide which ones to work on if time permits)

PR:

• https://github.com/sagemath/sage/pull/35870

[Carlxuzhl]

This issue will be used as a journal to note down my discussion with Prof. Koeppe on the GSoC 2023 project.

In the first week, our focus will be on #19219 and #35368 related to adding the CyLP backend, which will be implemented in Cython.

For the time being, we will just ignore GLPK(default solver in Sage) and PuLP.

[Carlxuzhl]

1. discussed how to collect examples from doctests and evaluate performance
2. specified what kind of plots is needed for the tiling solver

• command for searching for plots: git grep -i '[.][.] plot’

• examples of plots for documentations: src/sage/combinat/root_system/plot.py src/sage/graphs/graph_plot.py: .. PLOT:: src/sage/graphs/generators/families.py

[Carlxuzhl]

1. discussed how to handle segmentation fault of the doctests:

   • diagnose with the config.log file
   • check whether Xcode is up-to-date
   • try on Windows device (WSL)

2. optional command for doctests:

   • ./sage -tp —all
   • long
   • not tested
   • ./sage -t --long

Next steps:

• finish MatrixBackend from #35329
• run separate files/self-created files which are not in Sage doctests
• test with cvxpy backend and Cbc: make sage_numerical_backends_coin

[Carlxuzhl]

Module name	Total time for all tests	number of all tests and failures
sage/graphs/graph_coloring.pyx	1.7 seconds	[146 tests, 86 failures, 1.67 s]
sage/graphs/digraph.py	0.9 seconds
sage/combinat/bijectionist.py
sage/combinat/designs/incidence_structures.py	1.4 seconds	[338 tests, 216 failures, 1.29 s]
sage/combinat/designs/orthogonal_arrays.py	1.8 seconds	[182 tests, 110 failures, 1.72 s]
sage/combinat/designs/bibd.py	1.1 seconds	[134 tests, 97 failures, 1.02 s]
sage/combinat/matrices/dancing_links.pyx	2.7 seconds	[247 tests, 128 failures, 2.67 s]
sage/graphs/connectivity.pyx	8.4 seconds	[509 tests, 221 failures, 3.76 s]
sage/graphs/graph_decompositions/cutwidth.pyx	0.2 seconds	[63 tests, 24 failures, 0.20 s]
sage/graphs/domination.py	0.6 seconds	[104 tests, 59 failures, 0.57 s]
sage/combinat/integer_vector.py	0.9 seconds	[244 tests, 204 failures, 0.87 s]
sage/combinat/posets/posets.py	6.2 seconds	[1470 tests, 976 failures, 6.07 s]
sage/graphs/comparability.pyx	0.7 seconds	[52 tests, 31 failures, 0.67 s]
sage/graphs/graph_decompositions/vertex_separation.pyx	1.1 seconds	[186 tests, 76 failures, 1.10 s]
sage/graphs/bipartite_graph.py	2.7 seconds	[420 tests, 220 failures, 2.63 s]
sage/combinat/designs/orthogonal_arrays_build_recursive.py	5.7 seconds	[70 tests, 44 failures, 5.64 s]

[Carlxuzhl]

Module name	solver	Total time	solver	Total time	solver	Total time
sage/graphs/connectivity.pyx	Default(GLPK)	8.4 seconds	CBC (”Coin”)	8.2 seconds	CVXPY	8.0 seconds
sage/combinat/posets/posets.py	Default(GLPK)	6.2 seconds	CBC (”Coin”)	6.4 seconds	CVXPY	IOPub message rate exceeded.
sage/combinat/designs/orthogonal_arrays_build_recursive.py	Default(GLPK)	5.7 seconds	CBC (”Coin”)	5.7 seconds	CVXPY	5.6 seconds

[Carlxuzhl]

plans:

1. Change #35329 so that it uses Sage Matrix and Vector instead of Python lists (A new PR will be created and the link will be updated here)(updated: #35870)

2. Implement a variant of MatrixBackend that uses numpy arrays instead of a Sage matrix

3. Extend this to a new CVXpy backend in the given form

[Carlxuzhl]

I drafted a midterm evaluation write-up that includes reflections on the current progress and the revised schedule. (link: https://docs.google.com/document/d/1vZ-G04wk3epgH21B3kVKBNGzoemFNfTEox9wDaRZGik/edit?usp=sharing)