Opened 7 years ago
Closed 7 years ago
#18838 closed defect (fixed)
GLPK backend does not detect unboundedness in simplexonly mode
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  numerical  Keywords:  lp 
Cc:  yzh, ncohen, dimpase, john_perry, dcoudert  Merged in:  
Authors:  Matthias Koeppe, Yuan Zhou  Reviewers:  Dima Pasechnik, David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  b8daa1f (Commits, GitHub, GitLab)  Commit:  b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa 
Dependencies:  Stopgaps: 
Description (last modified by )
testcase:
sage: p = MixedIntegerLinearProgram(maximization=True, solver = "GLPK") sage: p.set_objective(p[0]) sage: p.solver_parameter("simplex_or_intopt", "simplex_only") sage: p.solve() 0.0
Change History (43)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 Changed 7 years ago by
 Cc ncohen added
comment:3 Changed 7 years ago by
 Branch set to u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode
comment:4 Changed 7 years ago by
 Commit set to 12f551692b849a4e899420ebcf8fccd3263ea0d7
 Status changed from new to needs_review
comment:5 Changed 7 years ago by
 Commit changed from 12f551692b849a4e899420ebcf8fccd3263ea0d7 to dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0
comment:6 Changed 7 years ago by
 Cc dimpase added
comment:7 followup: ↓ 12 Changed 7 years ago by
 Cc john_perry added
something worries me there:
status = glp_simplex(self.lp, self.smcp) status = glp_get_prim_stat(self.lp)
makes no sense to me... The ticket proposes to change the 2nd line to
status = glp_get_status(self.lp)
but still...
comment:8 Changed 7 years ago by
 Commit changed from dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0 to 597fabf87078fd708160a775b9ae0d215e3ac7a0
Branch pushed to git repo; I updated commit sha1. New commits:
597fabf  Include detailed error message for glp_simplex

comment:9 Changed 7 years ago by
 Commit changed from 597fabf87078fd708160a775b9ae0d215e3ac7a0 to 54c9bde659948677b63d8edd39f2a69f8549102a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
54c9bde  Include detailed error message for solve method

comment:10 Changed 7 years ago by
 Commit changed from 54c9bde659948677b63d8edd39f2a69f8549102a to 4092d3594525fa3e92d69bf09e2acf4708c3951e
Branch pushed to git repo; I updated commit sha1. New commits:
4092d35  Distinguish solve_status and solution_status for error status values

comment:11 Changed 7 years ago by
 Commit changed from 4092d3594525fa3e92d69bf09e2acf4708c3951e to e3f4f8706abcc93100dd110533296ea238bf4d13
Branch pushed to git repo; I updated commit sha1. New commits:
e3f4f87  Fix bug: solution_status is defined only if solve_status is 0.

comment:12 in reply to: ↑ 7 Changed 7 years ago by
Replying to dimpase:
something worries me there:
status = glp_simplex(self.lp, self.smcp) status = glp_get_prim_stat(self.lp)makes no sense to me... The ticket proposes to change the 2nd line to
status = glp_get_status(self.lp)but still...
The code now checks both the result of glp_simplex and of glp_get_status. Needs review.
comment:13 Changed 7 years ago by
comment:14 Changed 7 years ago by
 Status changed from needs_review to needs_work
docs don't build:
Error building the documentation. Traceback (most recent call last): File "/home/dima/software/sage/src/doc/common/builder.py", line 1626, in <module> getattr(get_builder(name), type)() File "/home/dima/software/sage/src/doc/common/builder.py", line 292, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/home/dima/software/sage/src/doc/common/builder.py", line 503, in _wrapper x.get(99999) File "/home/dima/software/sage/local/lib/python/multiprocessing/pool.py", line 558, in get raise self._value OSError: [numerical] docstring of sage.numerical.backends.glpk_backend.GLPKBackend.solve:82: ERROR: Unknown interpreted text role "ticket".
due to wrong tag ticket
in
Below we test that GLPK backend can detect unboundedness in simplexonly mode (:ticket:`18838`).
It should be
(:trac:`18838`).
there.
PS. Please check that your patches produce correct docs, before setting tickets up for review.
comment:15 Changed 7 years ago by
 Branch changed from u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode to u/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode
comment:16 Changed 7 years ago by
 Commit changed from e3f4f8706abcc93100dd110533296ea238bf4d13 to b0d61b80d471f24aa92a256e2fed8d7795ef1554
 Status changed from needs_work to needs_review
Docs build now; I took the opportunity to clean up the documentation a bit.
New commits:
b0d61b8  Fix documentation

comment:17 Changed 7 years ago by
(Should I be rebasing this on top of #18764?)
comment:18 Changed 7 years ago by
comment:19 Changed 7 years ago by
 Commit changed from b0d61b80d471f24aa92a256e2fed8d7795ef1554 to 7da8130a4c5fd59abc169c10382d2a7902573ca3
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7da8130  Detect unboundedness in GLPK backend simplexonly mode.

comment:20 Changed 7 years ago by
Rebased on top of current develop, which merged #18764.
comment:21 Changed 7 years ago by
 Reviewers set to Dima Pasechnik
comment:22 Changed 7 years ago by
 Status changed from needs_review to needs_work
This patch needs reworking on top of #18995 (which has been merged in current develop).
comment:23 Changed 7 years ago by
 Branch changed from u/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode to u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode
comment:24 Changed 7 years ago by
 Commit changed from 7da8130a4c5fd59abc169c10382d2a7902573ca3 to a25f47fa00d2fa7e5486f64405fa73b2ff3f909a
comment:25 Changed 7 years ago by
Patchbot reports that two tests fail:
sage t long src/sage/numerical/mip.pyx ********************************************************************** File "src/sage/numerical/mip.pyx", line 2416, in sage.numerical.mip.MIPSolverException.__init__ Failed example: p.solve() Expected: Traceback (most recent call last): ... MIPSolverException: 'GLPK : There is no feasible integer solution to this Linear Program' Got: <BLANKLINE> Traceback (most recent call last): File "/home/vincent/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/vincent/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.numerical.mip.MIPSolverException.__init__[7]>", line 1, in <module> p.solve() File "sage/numerical/mip.pyx", line 2098, in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:14050) self._backend.solve() File "sage/numerical/backends/glpk_backend.pyx", line 1018, in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.cpp:8533) raise MIPSolverException("GLPK : Solution is undefined. The LP (relaxation) problem instance has no primal feasible solution") MIPSolverException: 'GLPK : Solution is undefined. The LP (relaxation) problem instance has no primal feasible solution' ********************************************************************** File "src/sage/numerical/mip.pyx", line 2432, in sage.numerical.mip.MIPSolverException.__init__ Failed example: p.solve() Expected: Traceback (most recent call last): ... MIPSolverException: 'GLPK : There is no feasible integer solution to this Linear Program' Got: <BLANKLINE> Traceback (most recent call last): File "/home/vincent/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/vincent/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 858, in compile_and_execute exec(compiled, globs) File "<doctest sage.numerical.mip.MIPSolverException.__init__[14]>", line 1, in <module> p.solve() File "sage/numerical/mip.pyx", line 2098, in sage.numerical.mip.MixedIntegerLinearProgram.solve (build/cythonized/sage/numerical/mip.c:14050) self._backend.solve() File "sage/numerical/backends/glpk_backend.pyx", line 1018, in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.cpp:8533) raise MIPSolverException("GLPK : Solution is undefined. The LP (relaxation) problem instance has no primal feasible solution") MIPSolverException: 'GLPK : Solution is undefined. The LP (relaxation) problem instance has no primal feasible solution' ********************************************************************** 1 item had failures: 2 of 16 in sage.numerical.mip.MIPSolverException.__init__ [467 tests, 2 failures, 1.39 s]
comment:26 Changed 7 years ago by
 Commit changed from a25f47fa00d2fa7e5486f64405fa73b2ff3f909a to 5790ee300a245073a0c2695034236fc42e73f7b1
Branch pushed to git repo; I updated commit sha1. New commits:
5790ee3  Fix doctests

comment:27 Changed 7 years ago by
 Commit changed from 5790ee300a245073a0c2695034236fc42e73f7b1 to f7216d3fb84608fb531c8f803b5c46375dcbb628
Branch pushed to git repo; I updated commit sha1. New commits:
f7216d3  Better interface for error codes;

comment:28 Changed 7 years ago by
 Commit changed from f7216d3fb84608fb531c8f803b5c46375dcbb628 to de0dab2efdc995d94560708244312d1e72eba425
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
de0dab2  Detect unboundedness in GLPK backend simplexonly mode.

comment:29 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:30 Changed 7 years ago by
 Cc dcoudert added
comment:31 Changed 7 years ago by
This ticket is ready for review
comment:32 followup: ↓ 33 Changed 7 years ago by
When I click on the branch http://git.sagemath.org/sage.git/diff/?id=601346c9cd74a2860fbc75ba0a6350bf8f9f72c3 at the top of this page, so on
u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode
, I see only removals of tons of lines of code (i.e., removal of mip.pyx and glpk backend).
I don't understand why.
comment:33 in reply to: ↑ 32 Changed 7 years ago by
 Milestone changed from sage6.8 to sage6.9
That's weird. I have the same problem now, but it was fine few weeks ago. I change Miestone sage6.8 to sage6.9 in the ticket. Anyway, I find the correct diff here: http://git.sagemath.org/sage.git/diff/?h=u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode
comment:34 followup: ↓ 36 Changed 7 years ago by
Merge your branch with the latest beta (or rebase it), then push to the branch and it will go away.
Nathann
comment:35 Changed 7 years ago by
 Commit changed from de0dab2efdc995d94560708244312d1e72eba425 to 153805c76e3e0a33c28ec9a6ce0854209ffded1e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
153805c  Detect unboundedness in GLPK backend simplexonly mode.

comment:36 in reply to: ↑ 34 Changed 7 years ago by
Thanks Nathann. I rebased the ticket on top of the current develop.
comment:37 followup: ↓ 39 Changed 7 years ago by
 Reviewers changed from Dima Pasechnik to Dima Pasechnik, David Coudert
Much better now.
The patch passes all tests. I have however some remarks:
 Why are you removing
GLP_EOPFS
andGLP_EODFS
? (I don't know the meaning of these variables) This algorithm can be requested explicitly by setting the solver parameter "simplex_or_intopt" to "intopt_only".
The example following this statement does not examplify it. Where are you setting the solver parameter? comments should be formatted in 80 columns mode
comment:38 Changed 7 years ago by
 Commit changed from 153805c76e3e0a33c28ec9a6ce0854209ffded1e to 6e680f9b7f276182fc898a1f07238be80aa34bed
Branch pushed to git repo; I updated commit sha1. New commits:
6e680f9  format comments in 80 columns mode

comment:39 in reply to: ↑ 37 Changed 7 years ago by
Thanks for your remarks.
 Why are you removing
GLP_EOPFS
andGLP_EODFS
? (I don't know the meaning of these variables)
I remove GLP_EOPFS
and GLP_EODFS
because they are misspelled. They should be:
GLP_ENOPFS
: "The LP (relaxation) problem has no primal feasible solution";
GLP_ENODFS
: "The LP (relaxation) problem has no dual feasible solution",
This algorithm can be requested explicitly by setting the solver parameter "simplex_or_intopt" to "intopt_only".
The example following this statement does not examplify it. Where are you setting the solver parameter?
glp_intopt
is the default value for the solver parameter simplex_or_intopt
, unless all variables are continuous.
comment:40 Changed 7 years ago by
A small typo.
Thisroutine sometimes FAILS CATASTROPHICALLY
>This routine sometimes FAILS CATASTROPHICALLY
comment:41 Changed 7 years ago by
 Commit changed from 6e680f9b7f276182fc898a1f07238be80aa34bed to b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa
Branch pushed to git repo; I updated commit sha1. New commits:
b8daa1f  fix a typo

comment:42 Changed 7 years ago by
 Status changed from needs_review to positive_review
For me this patch is now good to go. Thanks. David.
comment:43 Changed 7 years ago by
 Branch changed from u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode to b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
More doctests for unboundedness in GLPK backend simplexonly mode.