Opened 4 years ago
Closed 4 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 4 years ago by
- Branch set to u/ncohen/18995
- Commit set to f8b8becf8511fc7b652866076b0a8ebc5dc3cb86
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 4 years ago by
Do any other backends suffer from the same issue?
comment:3 in reply to: ↑ 2 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
- Summary changed from Approximate LP solving: do not raise exceptions to Approximate LP solving with GLPK: do not raise exceptions
comment:6 Changed 4 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
Then the patch is good to go ;)
comment:7 Changed 4 years ago by
Thanks !
comment:8 Changed 4 years ago by
- Branch changed from u/ncohen/18995 to f8b8becf8511fc7b652866076b0a8ebc5dc3cb86
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
trac #18995: Approximate LP solving: do not raise exceptions