ENH: linalg/optimize: improved support for large, sparse problems

[mdhaber]

SciPy seeks to provide access

• from Python
• to implementations of fundamental scientific computing algorithms,
• especially when there is need unmet by other permissively-licensed packages.

This issue summarizes the status of SciPy's support for sparse linear algebra and optimization, and it details what I propose to add.

Linear Algebra

SciPy has some support for sparse linear algebra:

• SciPy vendors the permissively-licensed direct LU solver SuperLU.
• scipy.sparse.linalg.spsolve uses SuperLU unless scikit-umfpack can be imported, in which case it uses scikit-umfpack's interface to the GPL-licensed UMFPACK, the LU solver from SuiteSparse.
• SciPy vendors the permissively-licensed eigenvalue problem solver ARPACK and includes an implementation of LOBPCG.
• scipy.sparse.linalg provides interfaces to these for solving eigenvalue and singular value problems.
• SciPy includes many iterative methods for solving sparse linear systems.

SciPy lacks sparse support for other fundamental linear algebra algorithms, most notably Cholesky decomposition and QR decomposition. Also, better support for sparse SVD has been desired for years (gh-857). There is some support for solving these problems in the greater scientific Python ecosystem, but there are also unmet needs. Following the model of SciPy's scipy.sparse.linalg.spsolve, my goal is to enable easy access to both permissively-licensed implementations and more performant (potentially copyleft-licensed) implementations of algorithms for these problems from Linux, Mac, and (the oft forgotten) Windows.

• scikit-sparse provides an interface to the LGPL-licensed CHOLMOD, the Cholesky routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below), and scikit-sparse does not appear to be actively maintained. I propose to

  • add a permissively-licensed sparse Cholesky implementation to SciPy using the ideas (not the code) from Tim Davis' book Direct Methods for Sparse Linear Systems.
  • ensure that there is an actively maintained wrapper for CHOLMOD that can be installed on Linux, Mac, and Windows. This may mean reviving scikit-sparse, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.sparse.linalg interface to both the permissively-licensed implementation and the more performant CHOLMOD.

• sparseqr/PySPQR provides an interface to the GPL-licensed SPQR, the QR routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below). I propose to:

  • add a permissively-licensed sparse QR implementation to SciPy using the ideas (not the code) from Tim Davis' book Direct Methods for Sparse Linear Systems.
  • ensure that there is an actively maintained wrapper for SPQR that can be installed on Linux, Mac, and Windows. This may mean working with sparseqr/PySPQR, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.sparse.linalg interface to both the permissively-licensed implementation and the more performant SPQR.

• scikit-umfpack provides an interface to the GPL-licensed UMFPACK, the LU routines from SuiteSparse. However, installation on Windows is problematic (see Installation Notes below), and scikit-umfpack does not appear to be actively maintained. I propose to:

  • ensure that there is an actively maintained wrapper for UMFPACK that can be installed on Linux, Mac, and Windows. This may mean reviving scikit-umfpack, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.

• For improved sparse SVD support, @WarrenWeckesser has also indicated interest in vendoring PROPACK, finishing the pypropack wrapper, and including an interface in scipy.sparse.linalg.svd

Optimization

SciPy has some support for sparse optimization: scipy.optimize.minimize(method='trust-constr') and scipy.optimize.linprog(method='interior-point') exploit sparsity, and SciPy 1.6 will vendor the linear programming software HiGHS and add an interface via linprog. However, these offerings are substantially less powerful than copyleft-licensed counterparts, and convenient Python interfaces to the copyleft software is not available on all platforms. Following the model of SciPy's scipy.sparse.linalg.spsolve, my goal is to enable access to both permissively-licensed implementations and more performant (potentially copyleft-licensed) implementations of these solvers from Mac, Linux, and Windows.

• CyLP provides an interface to COIN-OR's Eclipse 2.0-licensed linear and mixed-integer program solvers, including CLP (the highest performance open-source linear programming solver) and CBC (one of the best open-source mixed-integer programming solvers). Installation on Windows is easy via pip, but is not available via conda. Also, the interface uses a modeling language approach rather than the direct approach more familiar to users of Matlab and SciPy, and the documentation is not very friendly. I propose to:

  • ensure that there is an actively maintained wrapper for CLP/CBC that can be installed on Linux, Mac, and Windows. This may mean working with CyLP, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.optimize interface to the CLP/CBC solvers.
  • add a scipy.optimize interface to HiGHS' mixed-integer programming capabilities.

• cyipopt and Gekko both provide interfaces to COIN-OR's Eclipse 2.0-licensed nonlinear programming solver IPOPT, the highest performance open-source linear programming solver. Installation of cyipopt on Windows is problematic (see Installation Notes below), and Gekko's interface uses a modeling language approach rather than the direct approach more familiar to users of Matlab and SciPy. I propose to:

  • ensure that there is an actively maintained wrapper for IPOPT that can be installed on Linux, Mac, and Windows. This may mean working with cyipopt, creating a new scikit, or (if desired and possible, given licenses) adding wrapper code directly to SciPy. @mckib2 has expressed interest in supporting this.
  • add a scipy.minimize interface to IPOPT.

Installation Notes

Notes from attempts to install the software above on Windows 11/30/2020:

• conda install suitesparse works
• conda install -c conda-forge scikit-umfpack fails
• pip install scikit-umfpack reports success, but from scikits import umfpack fails
• conda install -c conda-forge scikit-sparse fails
• pip install scikit-sparse fails
• sparseqr is not available on conda-forge
• pip install git+https://github.com/yig/PySPQR.git fails
• pip install sparseqr fails
• pip install cylp works, and the software works
• cylp is not available on conda-forge
• pip install ortools works, and the software works
• conda install -c conda-forge ipopt works
• conda install -c conda-forge cyipopt fails
• pip install ipopt fails

[mckib2]

@mdhaber is there a wishlist ranking of projects, i.e. what makes sense to prioritize first?

I've updated the HiGHS wrappers (waiting on some bug fixes to open a PR), but it leaves me in the position to start looking at a MIP interface for HiGHS (and presumably the rest of the MIP solvers mentioned here)

[mdhaber]

I wrote this up for @rgommers based on what we had written for the CZI Cycle 3 proposal and what I'd most like to do for the NASA ROSES opportunity. There's no need to get started on anything yet, but yes, we could start looking into those other HiGHS features we've discussed.

[rgommers]

It's pretty difficult to figure out what to prioritize I think. Based on what I'd expect the effort to be plus licensing constraints and future maintenance considerations, my opinion would be:

1. BSD-licensed functionality that can be wrapped - PROPACK, HiGHS
2. Fix up issues with separate sparse wrappers - scikit-umfpack, scikit-sparse, one of the sparse qr options
3. One of the CLP/CBC interface options
4. Writing sparse Cholesky from scratch

[mdhaber]

Sure, I can add more HiGHS work to the list. There are a lot of features they've had that we'd like to wrap (dual problem / sensitivity analysis information and MPS format conversion), and they recently merged a MIP solver into master.

[mckib2]

@mdhaber FYI, MPS writer is already available as a development debugging tool in scipy.optimize._highs, just needs a public API. The HiGHS reader should be similarly easy to wrap. The hard part here is making tests

[mckib2]

@mdhaber I have a HiGHS MIP wrapper working in a branch of my HiGHS fork.

Major changes:

• add intcon argument to highs_wrapper to give the index of integer-valued variables
• accept new MIP options, most notably mip_feasibility_tolerance (there are more and another set of message levels we'll have to figure out...)
• toggles between LP and MIP solver if intcon is nonempty. We can set this manually, but MIP seems to crash if mip=True and intcon is empty, so I'm doing the thing that makes it not crash

I only tested on a few small examples and I expect it will require a lot more testing and debugging.

I would like to wait until https://github.com/scipy/scipy/pull/13197 is merged before I start on another PR because my changes are based on updates in the existing PR.

[mdhaber]

Ok. I can't really work on optimize right now, though : / There is too much to finish on stats. When this project is done, though, I'll take a look.

[rgommers]

I have a HiGHS MIP wrapper working in a branch of my HiGHS fork.

That sounds great!

I would like to wait until scipy#13197 is merged before I start on another PR because my changes are based on updates in the existing PR.

You can always base one PR on the other one - it'll have duplicate commits, but those will disappear as soon as PR 1 is merged.

[rgommers]

@mdhaber it would be nice to move this content, which will be useful long-term, into a couple of issues on the main repo. Maybe one for sparse and one for optimize, as tracking issues for external libraries that we'd like to have wrappers/interfaces for?