Opened 3 years ago

Closed 3 years ago

#18995 closed defect (fixed)

Approximate LP solving with GLPK: do not raise exceptions

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.9
Component: numerical Keywords:
Cc: dimpase, dcoudert, nmaster@… Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: f8b8bec (Commits) Commit: f8b8becf8511fc7b652866076b0a8ebc5dc3cb86
Dependencies: Stopgaps:

Description

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.

Change History (8)

comment:1 Changed 3 years ago by ncohen

  • Branch set to u/ncohen/18995
  • Commit set to f8b8becf8511fc7b652866076b0a8ebc5dc3cb86
  • Status changed from new to needs_review

New commits:

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

comment:2 follow-up: Changed 3 years ago by dimpase

Do any other backends suffer from the same issue?

comment:3 in reply to: ↑ 2 Changed 3 years ago by ncohen

Do any other backends suffer from the same issue?

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

Nathann

comment:4 Changed 3 years ago by 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.

comment:5 Changed 3 years ago by ncohen

  • Summary changed from Approximate LP solving: do not raise exceptions to Approximate LP solving with GLPK: do not raise exceptions

comment:6 Changed 3 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

Then the patch is good to go ;)

comment:7 Changed 3 years ago by ncohen

Thanks !

comment:8 Changed 3 years ago by vbraun

  • Branch changed from u/ncohen/18995 to f8b8becf8511fc7b652866076b0a8ebc5dc3cb86
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.