Opened 4 years ago

Closed 4 years ago

#18838 closed defect (fixed)

GLPK backend does not detect unboundedness in simplex-only mode

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-6.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) Commit: b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa
Dependencies: Stopgaps:

Description (last modified by yzh)

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 4 years ago by yzh

  • Description modified (diff)

comment:2 Changed 4 years ago by ncohen

  • Cc ncohen added

comment:3 Changed 4 years ago by yzh

  • Branch set to u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode

comment:4 Changed 4 years ago by yzh

  • Commit set to 12f551692b849a4e899420ebcf8fccd3263ea0d7
  • Status changed from new to needs_review

comment:5 Changed 4 years ago by git

  • Commit changed from 12f551692b849a4e899420ebcf8fccd3263ea0d7 to dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0

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

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

comment:6 Changed 4 years ago by mkoeppe

  • Cc dimpase added

comment:7 follow-up: Changed 4 years ago by dimpase

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

Last edited 4 years ago by dimpase (previous) (diff)

comment:8 Changed 4 years ago by git

  • Commit changed from dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0 to 597fabf87078fd708160a775b9ae0d215e3ac7a0

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

597fabfInclude detailed error message for glp_simplex

comment:9 Changed 4 years ago by git

  • Commit changed from 597fabf87078fd708160a775b9ae0d215e3ac7a0 to 54c9bde659948677b63d8edd39f2a69f8549102a

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

54c9bdeInclude detailed error message for solve method

comment:10 Changed 4 years ago by git

  • Commit changed from 54c9bde659948677b63d8edd39f2a69f8549102a to 4092d3594525fa3e92d69bf09e2acf4708c3951e

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

4092d35Distinguish solve_status and solution_status for error status values

comment:11 Changed 4 years ago by git

  • Commit changed from 4092d3594525fa3e92d69bf09e2acf4708c3951e to e3f4f8706abcc93100dd110533296ea238bf4d13

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

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

comment:12 in reply to: ↑ 7 Changed 4 years ago by 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.

comment:13 Changed 4 years ago by mkoeppe

  • Authors set to Yuan Zhou

comment:14 Changed 4 years ago by dimpase

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

comment:15 Changed 4 years ago by mkoeppe

  • 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 4 years ago by mkoeppe

  • 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:

b0d61b8Fix documentation

comment:17 Changed 4 years ago by mkoeppe

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

comment:18 Changed 4 years ago by yzh

  • Authors changed from Yuan Zhou to Matthias Koeppe, Yuan Zhou

comment:19 Changed 4 years ago by git

  • Commit changed from b0d61b80d471f24aa92a256e2fed8d7795ef1554 to 7da8130a4c5fd59abc169c10382d2a7902573ca3

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

7da8130Detect unboundedness in GLPK backend simplex-only mode.

comment:20 Changed 4 years ago by mkoeppe

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

comment:21 Changed 4 years ago by mkoeppe

  • Reviewers set to Dima Pasechnik

comment:22 Changed 4 years ago by mkoeppe

  • 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 4 years ago by yzh

  • 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 4 years ago by yzh

  • Commit changed from 7da8130a4c5fd59abc169c10382d2a7902573ca3 to a25f47fa00d2fa7e5486f64405fa73b2ff3f909a

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


New commits:

a25f47fDetect unboundedness in GLPK backend simplex-only mode.

comment:25 Changed 4 years ago by 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]

comment:26 Changed 4 years ago by git

  • Commit changed from a25f47fa00d2fa7e5486f64405fa73b2ff3f909a to 5790ee300a245073a0c2695034236fc42e73f7b1

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

5790ee3Fix doctests

comment:27 Changed 4 years ago by git

  • Commit changed from 5790ee300a245073a0c2695034236fc42e73f7b1 to f7216d3fb84608fb531c8f803b5c46375dcbb628

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

f7216d3Better interface for error codes;

comment:28 Changed 4 years ago by git

  • Commit changed from f7216d3fb84608fb531c8f803b5c46375dcbb628 to de0dab2efdc995d94560708244312d1e72eba425

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

de0dab2Detect unboundedness in GLPK backend simplex-only mode.

comment:29 Changed 4 years ago by yzh

  • Status changed from needs_work to needs_review

comment:30 Changed 4 years ago by mkoeppe

  • Cc dcoudert added

comment:31 Changed 4 years ago by mkoeppe

This ticket is ready for review

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

comment:33 in reply to: ↑ 32 Changed 4 years ago by yzh

  • Milestone changed from sage-6.8 to sage-6.9

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

comment:34 follow-up: Changed 4 years ago by ncohen

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

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:35 Changed 4 years ago by git

  • Commit changed from de0dab2efdc995d94560708244312d1e72eba425 to 153805c76e3e0a33c28ec9a6ce0854209ffded1e

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

153805cDetect unboundedness in GLPK backend simplex-only mode.

comment:36 in reply to: ↑ 34 Changed 4 years ago by yzh

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

comment:37 follow-up: Changed 4 years ago by dcoudert

  • 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 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

comment:38 Changed 4 years ago by git

  • Commit changed from 153805c76e3e0a33c28ec9a6ce0854209ffded1e to 6e680f9b7f276182fc898a1f07238be80aa34bed

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

6e680f9format comments in 80 columns mode

comment:39 in reply to: ↑ 37 Changed 4 years ago by 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.

Last edited 4 years ago by yzh (previous) (diff)

comment:40 Changed 4 years ago by dcoudert

A small typo.

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

comment:41 Changed 4 years ago by git

  • Commit changed from 6e680f9b7f276182fc898a1f07238be80aa34bed to b8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa

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

b8daa1ffix a typo

comment:42 Changed 4 years ago by dcoudert

  • Status changed from needs_review to positive_review

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

comment:43 Changed 4 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.