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

Priority:  major  Milestone:  sage6.9 
Component:  numerical  Keywords:  lp 
Cc:  Yuan Zhou, Nathann Cohen, Dima Pasechnik, john_perry, David Coudert  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:  Nathann Cohen added 

comment:3 Changed 7 years ago by
Branch:  → u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode 

comment:4 Changed 7 years ago by
Commit:  → 12f551692b849a4e899420ebcf8fccd3263ea0d7 

Status:  new → needs_review 
comment:5 Changed 7 years ago by
Commit:  12f551692b849a4e899420ebcf8fccd3263ea0d7 → dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0 

comment:6 Changed 7 years ago by
Cc:  Dima Pasechnik 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:  dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0 → 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:  597fabf87078fd708160a775b9ae0d215e3ac7a0 → 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:  54c9bde659948677b63d8edd39f2a69f8549102a → 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:  4092d3594525fa3e92d69bf09e2acf4708c3951e → 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 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
Authors:  → Yuan Zhou 

comment:14 Changed 7 years ago by
Status:  needs_review → 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:  u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode → u/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode 

comment:16 Changed 7 years ago by
Commit:  e3f4f8706abcc93100dd110533296ea238bf4d13 → b0d61b80d471f24aa92a256e2fed8d7795ef1554 

Status:  needs_work → needs_review 
Docs build now; I took the opportunity to clean up the documentation a bit.
New commits:
b0d61b8  Fix documentation

comment:18 Changed 7 years ago by
Authors:  Yuan Zhou → Matthias Koeppe, Yuan Zhou 

comment:19 Changed 7 years ago by
Commit:  b0d61b80d471f24aa92a256e2fed8d7795ef1554 → 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:21 Changed 7 years ago by
Reviewers:  → Dima Pasechnik 

comment:22 Changed 7 years ago by
Status:  needs_review → 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:  u/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode → u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode 

comment:24 Changed 7 years ago by
Commit:  7da8130a4c5fd59abc169c10382d2a7902573ca3 → 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:  a25f47fa00d2fa7e5486f64405fa73b2ff3f909a → 5790ee300a245073a0c2695034236fc42e73f7b1 

Branch pushed to git repo; I updated commit sha1. New commits:
5790ee3  Fix doctests

comment:27 Changed 7 years ago by
Commit:  5790ee300a245073a0c2695034236fc42e73f7b1 → 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:  f7216d3fb84608fb531c8f803b5c46375dcbb628 → 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:  needs_work → needs_review 

comment:30 Changed 7 years ago by
Cc:  David Coudert added 

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 Changed 7 years ago by
Milestone:  sage6.8 → 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 and it will go away.
Nathann
comment:35 Changed 7 years ago by
Commit:  de0dab2efdc995d94560708244312d1e72eba425 → 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 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:  Dima Pasechnik → 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:  153805c76e3e0a33c28ec9a6ce0854209ffded1e → 6e680f9b7f276182fc898a1f07238be80aa34bed 

Branch pushed to git repo; I updated commit sha1. New commits:
6e680f9  format comments in 80 columns mode

comment:39 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:  6e680f9b7f276182fc898a1f07238be80aa34bed → b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa 

Branch pushed to git repo; I updated commit sha1. New commits:
b8daa1f  fix a typo

comment:42 Changed 7 years ago by
Status:  needs_review → positive_review 

For me this patch is now good to go. Thanks. David.
comment:43 Changed 7 years ago by
Branch:  u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode → b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
More doctests for unboundedness in GLPK backend simplexonly mode.