GLPK backend does not detect unboundedness in simplex-only mode

[mkoeppe]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dc441f2

More doctests for unboundedness in GLPK backend simplex-only mode.

[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...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​597fabf

Include detailed error message for glp_simplex

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​54c9bde

Include detailed error message for solve method

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4092d35

Distinguish solve_status and solution_status for error status values

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e3f4f87

Fix bug: solution_status is defined only if solve_status is 0.

[mkoeppe]

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.

[dimpase]

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 simplex-only mode (:ticket:`18838`).

It should be

(:trac:`18838`).

there.

PS. Please check that your patches produce correct docs, before setting tickets up for review.

[mkoeppe]

Docs build now; I took the opportunity to clean up the documentation a bit.

---

New commits:

​b0d61b8

Fix documentation

[mkoeppe]

(Should I be rebasing this on top of #18764?)

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​7da8130

Detect unboundedness in GLPK backend simplex-only mode.

[mkoeppe]

Rebased on top of current develop, which merged #18764.

[mkoeppe]

This patch needs reworking on top of #18995 (which has been merged in current develop).

[yzh]

Rebased on top of current develop, which merged #18995.

---

New commits:

​a25f47f

Detect unboundedness in GLPK backend simplex-only mode.

[mkoeppe]

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/site-packages/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/site-packages/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/site-packages/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/site-packages/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]

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5790ee3

Fix doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f7216d3

Better interface for error codes;

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​de0dab2

Detect unboundedness in GLPK backend simplex-only mode.

[mkoeppe]

This ticket is ready for review

[dcoudert]

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.

[yzh]

That's weird. I have the same problem now, but it was fine few weeks ago. I change Miestone sage-6.8 to sage-6.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

[ncohen]

Merge your branch with the latest beta (or rebase it), then push to the branch and it will go away.

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​153805c

Detect unboundedness in GLPK backend simplex-only mode.

[yzh]

Thanks Nathann. I rebased the ticket on top of the current develop.

[dcoudert]

Much better now.

The patch passes all tests. I have however some remarks:

• Why are you removing GLP_EOPFS and GLP_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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6e680f9

format comments in 80 columns mode

[yzh]

Thanks for your remarks.

• Why are you removing GLP_EOPFS and GLP_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.

[dcoudert]

A small typo.

• Thisroutine sometimes FAILS CATASTROPHICALLY-> This routine sometimes FAILS CATASTROPHICALLY

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b8daa1f

fix a typo

[dcoudert]

For me this patch is now good to go. Thanks. David.