search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

`MixedIntegerLinearProgram`: Add `matrix_backend` (dummy solver) #35308

Open mkoeppe opened 1 year ago

mkoeppe commented 1 year ago

Is there an existing issue for this?

Problem Description

A MixedIntegerLinearProgram is a good way to set up a linear inequality system, sort of as a lazy H-polyhedron. But this depends on a solver -- so it can only be used with base_ring=QQ.

Proposed Solution

To generalize this, we should create a new module sage.numerical.backends.matrix_backend, a dummy solver that only stores the data (in Sage matrices and vectors) and can handle arbitrary base rings. (This is similar to the existing .matrix_sdp_backend.)

Alternatives Considered

Lazy polyhedra.

Additional Information

No response

jnash10 commented 1 year ago

After scanning the files, I had the following doubts, could you please clear them whenever you have the time, thanks!

  1. In the definition of MixedIntegerLinearProgram : https://github.com/sagemath/sage/blob/c00e6c204b2d0e1fe1314ec497cdab0b03dd92e3/src/sage/numerical/mip.pxd#L11-L26 I couldn't see where a solver was required to define the class.
  2. Since it inherits from the SageObject class, I checked if that requires a solver and couldn't find anything. Seems like SageObject just ensures that the object doesn't break existing Sage code and follows all required basic standards with some basic functions.
  3. Since we also import the GenericBackend class, the instances of solve there were: https://github.com/sagemath/sage/blob/c00e6c204b2d0e1fe1314ec497cdab0b03dd92e3/src/sage/numerical/backends/generic_backend.pxd#L27 , https://github.com/sagemath/sage/blob/c00e6c204b2d0e1fe1314ec497cdab0b03dd92e3/src/sage/numerical/backends/generic_backend.pxd#L48 and https://github.com/sagemath/sage/blob/c00e6c204b2d0e1fe1314ec497cdab0b03dd92e3/src/sage/numerical/backends/generic_backend.pxd#L60 where an object was created from the class and a solver is required. Yet I couldn't pinpoint were we set it as a requirement in the class definition.
  4. Can we create a modified version of GenericBackend to not require the solver and use that to create the MixedIntegerLinearProgram similar to matrix_sdp_backend as you mentioned? In that case what additional methods does the class require.

I might not make sense at a few places, I hope you excuse that, and I'd be grateful for the corrections.

Thanks for your time!

mkoeppe commented 1 year ago

Backends are implemented by subclassing GenericBackend. For example, see https://github.com/sagemath/sage/blob/develop/src/sage/numerical/backends/scip_backend.pyx