MixedIntegerLinearProgram: Add matrix_backend (dummy solver)

[mkoeppe]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

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]

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 :

   sage/src/sage/numerical/mip.pxd

   Lines 11 to 26 in c00e6c2

   	cdef class MixedIntegerLinearProgram(SageObject):
   	cdef GenericBackend _backend
   	cdef list _first_variable_names
   	cdef list _mipvariables
   	cdef MIPVariable _default_mipvariable
   	cdef dict _variables
   	cdef int __BINARY
   	cdef int __REAL
   	cdef int __INTEGER
   	cdef object _linear_functions_parent
   	cdef object _linear_constraints_parent
   	cpdef int number_of_constraints(self)
   	cpdef int number_of_variables(self)
   	cdef int _check_redundant
   	cdef list _constraints
   	cpdef sum(self, L)

   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:

   sage/src/sage/numerical/backends/generic_backend.pxd

   Line 27 in c00e6c2

   cpdef int solve(self) except -1

   ,

   sage/src/sage/numerical/backends/generic_backend.pxd

   Line 48 in c00e6c2

   cpdef solver_parameter(self, name, value=*)

   and

   sage/src/sage/numerical/backends/generic_backend.pxd

   Line 60 in c00e6c2

   cpdef GenericBackend get_solver(constraint_generation = ?, solver = ?, base_ring = ?)

   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]

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