Approximate LP solving with GLPK: do not raise exceptions

[ncohen]

It has been reported by Neal Master that when solving a LP with a time limit or an optimality gap, an exception was raised whenever the solution was ... not optimal.

Which is precisely why people solve problems with such limits: to get a solution when getting an optimal one is too hard.

With this patch, no exception is raised in such situations. And two new doctests are added.

[ncohen]

New commits:

​f8b8bec

trac #18995: Approximate LP solving: do not raise exceptions

[dimpase]

Do any other backends suffer from the same issue?

[ncohen]

Do any other backends suffer from the same issue?

No idea. Unfortunately, I was not able to write a solver-independent doctest.

Nathann

[dcoudert]

I have used many times time limits and optimality gaps with cplex without difficulties.

sage: from sage.numerical.mip import MixedIntegerLinearProgram
sage: g = graphs.CubeGraph(9)
sage: p = MixedIntegerLinearProgram(solver="Cplex")
sage: p.solver_parameter("CPX_PARAM_EPAGAP", 100)
sage: b = p.new_variable(binary=True)
sage: p.set_objective(p.sum(b[v] for v in g))
sage: for v in g:
....:     p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1)
....:     
sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution
sage: p.solve()
28.0

With Coin, we don't have access to optimality gap or timelimit.

sage: p = MixedIntegerLinearProgram(solver="Coin")
sage: p.solver_parameter("mip_gap_tolerance",100)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-25-b082f5cd7a90> in <module>()
----> 1 p.solver_parameter("mip_gap_tolerance",Integer(100))

/Users/dcoudert/sage/src/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter (/Users/dcoudert/sage/src/build/cythonized/sage/numerical/mip.c:14957)()
   2303             return self._backend.solver_parameter(name)
   2304         else:
-> 2305             self._backend.solver_parameter(name, value)
   2306 
   2307     cpdef sum(self, L):

/Users/dcoudert/sage/src/sage/numerical/backends/generic_backend.pyx in sage.numerical.backends.generic_backend.GenericBackend.solver_parameter (/Users/dcoudert/sage/src/build/cythonized/sage/numerical/backends/generic_backend.c:7780)()
    907             sage: p.solver_parameter("timelimit")                   # optional - Nonexistent_LP_solver
    908         """
--> 909         raise NotImplementedError()
    910 
    911 

NotImplementedError: 

This patch is working well and passes all tests, but you could change the ticket description to say that it solves the issue for GLPK only.

[dcoudert]

Then the patch is good to go ;)

[ncohen]

Thanks !