Opened 7 years ago

Closed 7 years ago

#18838 closed defect (fixed)

GLPK backend does not detect unboundedness in simplex-only mode

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by Yuan Zhou)

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 Yuan Zhou

Description: modified (diff)

comment:2 Changed 7 years ago by Nathann Cohen

Cc: Nathann Cohen added

comment:3 Changed 7 years ago by Yuan Zhou

Branch: u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode

comment:4 Changed 7 years ago by Yuan Zhou

Commit: 12f551692b849a4e899420ebcf8fccd3263ea0d7
Status: newneeds_review

comment:5 Changed 7 years ago by git

Commit: 12f551692b849a4e899420ebcf8fccd3263ea0d7dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0

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

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

comment:6 Changed 7 years ago by Matthias Köppe

Cc: Dima Pasechnik added

comment:7 Changed 7 years ago by Dima Pasechnik

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 7 years ago by Dima Pasechnik (previous) (diff)

comment:8 Changed 7 years ago by git

Commit: dc441f2cd0871754ce1e9b4e5ec97dcb86e667d0597fabf87078fd708160a775b9ae0d215e3ac7a0

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

597fabfInclude detailed error message for glp_simplex

comment:9 Changed 7 years ago by git

Commit: 597fabf87078fd708160a775b9ae0d215e3ac7a054c9bde659948677b63d8edd39f2a69f8549102a

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 7 years ago by git

Commit: 54c9bde659948677b63d8edd39f2a69f8549102a4092d3594525fa3e92d69bf09e2acf4708c3951e

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

4092d35Distinguish solve_status and solution_status for error status values

comment:11 Changed 7 years ago by git

Commit: 4092d3594525fa3e92d69bf09e2acf4708c3951ee3f4f8706abcc93100dd110533296ea238bf4d13

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 7 years ago by Matthias Köppe

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 Matthias Köppe

Authors: Yuan Zhou

comment:14 Changed 7 years ago by Dima Pasechnik

Status: needs_reviewneeds_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 7 years ago by Matthias Köppe

Branch: u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_modeu/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode

comment:16 Changed 7 years ago by Matthias Köppe

Commit: e3f4f8706abcc93100dd110533296ea238bf4d13b0d61b80d471f24aa92a256e2fed8d7795ef1554
Status: needs_workneeds_review

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


New commits:

b0d61b8Fix documentation

comment:17 Changed 7 years ago by Matthias Köppe

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

comment:18 Changed 7 years ago by Yuan Zhou

Authors: Yuan ZhouMatthias Koeppe, Yuan Zhou

comment:19 Changed 7 years ago by git

Commit: b0d61b80d471f24aa92a256e2fed8d7795ef15547da8130a4c5fd59abc169c10382d2a7902573ca3

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 7 years ago by Matthias Köppe

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

comment:21 Changed 7 years ago by Matthias Köppe

Reviewers: Dima Pasechnik

comment:22 Changed 7 years ago by Matthias Köppe

Status: needs_reviewneeds_work

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

comment:23 Changed 7 years ago by Yuan Zhou

Branch: u/mkoeppe/glpk_backend_does_not_detect_unboundedness_in_simplex_only_modeu/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_mode

comment:24 Changed 7 years ago by Yuan Zhou

Commit: 7da8130a4c5fd59abc169c10382d2a7902573ca3a25f47fa00d2fa7e5486f64405fa73b2ff3f909a

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


New commits:

a25f47fDetect unboundedness in GLPK backend simplex-only mode.

comment:25 Changed 7 years ago by Matthias Köppe

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 7 years ago by git

Commit: a25f47fa00d2fa7e5486f64405fa73b2ff3f909a5790ee300a245073a0c2695034236fc42e73f7b1

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

5790ee3Fix doctests

comment:27 Changed 7 years ago by git

Commit: 5790ee300a245073a0c2695034236fc42e73f7b1f7216d3fb84608fb531c8f803b5c46375dcbb628

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

f7216d3Better interface for error codes;

comment:28 Changed 7 years ago by git

Commit: f7216d3fb84608fb531c8f803b5c46375dcbb628de0dab2efdc995d94560708244312d1e72eba425

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 7 years ago by Yuan Zhou

Status: needs_workneeds_review

comment:30 Changed 7 years ago by Matthias Köppe

Cc: David Coudert added

comment:31 Changed 7 years ago by Matthias Köppe

This ticket is ready for review

comment:32 Changed 7 years ago by David Coudert

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 Yuan Zhou

Milestone: sage-6.8sage-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 Changed 7 years ago by Nathann Cohen

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

Nathann

Last edited 7 years ago by Nathann Cohen (previous) (diff)

comment:35 Changed 7 years ago by git

Commit: de0dab2efdc995d94560708244312d1e72eba425153805c76e3e0a33c28ec9a6ce0854209ffded1e

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 7 years ago by Yuan Zhou

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

comment:37 Changed 7 years ago by David Coudert

Reviewers: Dima PasechnikDima 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 7 years ago by git

Commit: 153805c76e3e0a33c28ec9a6ce0854209ffded1e6e680f9b7f276182fc898a1f07238be80aa34bed

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

6e680f9format comments in 80 columns mode

comment:39 in reply to:  37 Changed 7 years ago by Yuan Zhou

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 7 years ago by Yuan Zhou (previous) (diff)

comment:40 Changed 7 years ago by David Coudert

A small typo.

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

comment:41 Changed 7 years ago by git

Commit: 6e680f9b7f276182fc898a1f07238be80aa34bedb8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa

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

b8daa1ffix a typo

comment:42 Changed 7 years ago by David Coudert

Status: needs_reviewpositive_review

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

comment:43 Changed 7 years ago by Volker Braun

Branch: u/yzh/glpk_backend_does_not_detect_unboundedness_in_simplex_only_modeb8daa1f042bd5d73f3d2cefed7c9db0db71ef7fa
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.