wrong/misleading error message using MixedIntegerLinearProgram/GLPK

[galipnik]

The following code leads to an error message which seems to be incorrect (or at least misleading...): MIPSolverException: GLPK: Problem has no feasible solution.

• The MILP has a feasible solution, at least the zero vector is feasible.
• If I set x.set_max(10^5) (something smaller than 10^25), everything works fine.

sage: A = matrix([
....: [ 1,  1,  1,  0,  0,  0,  0, -1,  0, -1,  0,  0,  0,  0,  0, -1,  0,  0,  0,  0],
....: [ 0,  0,  0,  1,  1,  1,  1,  0, -1,  0, -1,  0, -1,  0,  0,  0,  0, -1,  0,  0],
....: [-1,  0,  0, -1,  0,  0,  0,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
....: [ 0, -1,  0,  0, -1,  0,  0,  0,  0,  1,  1,  1,  0,  0,  0,  0,  0,  0, -1,  0],
....: [ 0,  0,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  1,  1,  1,  0, -1,  0,  0, -1],
....: [ 0,  0, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  1,  1,  0,  0,  0],
....: [ 0,  0,  0,  0,  0,  0, -1,  0,  0,  0,  0, -1,  0,  0, -1,  0,  0,  1,  1,  1],
....: [ 1,  1,  1,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  0],
....: [-1,  0,  0,  1,  1,  1,  1, -1,  0,  0,  0, -1,  0,  0,  0,  0,  0,  0, -1,  0],
....: [ 0,  0,  0,  0, -1,  0,  0,  1,  1,  0, -1,  0,  0,  0, -1,  0,  0,  0,  0, -1],
....: [ 0,  0,  0,  0,  0, -1,  0,  0,  0,  1,  1,  1, -1,  0,  0,  0,  0,  0,  0,  0],
....: [ 0,  0, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1, -1,  0,  0,  0,  0],
....: [ 0, -1,  0, -1,  0,  0,  0,  0, -1, -1,  0,  0,  0,  0,  0,  1,  1,  0,  0,  0],
....: [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1,  0,  0, -1,  1,  1,  1]])
sage: P = MixedIntegerLinearProgram(maximization=True, solver="GLPK")
sage: x = P.new_variable(integer=True, nonnegative=True)
sage: x.set_max(10^25)
sage: P.set_objective(sum(x[i] for i in srange(20)))
sage: for i in srange(14):
....:     P.add_constraint(sum(x[j]*A[i][j] for j in srange(20)) == 0)
sage: P.solve()
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
...
/.../sage-8.9/local/lib/python2.7/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:9658)()
   1074             raise MIPSolverException("GLPK: "+solve_status_msg.get(solve_status, "unknown error during call to GLPK : "+str(solve_status)))
   1075         else:
-> 1076             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
   1077         return 0
   1078 

MIPSolverException: GLPK: Problem has no feasible solution

(observe unknown error during call to GLPK)

Component: linear programming

Issue created by migration from https://trac.sagemath.org/ticket/29254

[galipnik]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-The following code leads to an error message which seems to be incorrect (or *at least misleading*...): "MIPSolverException: GLPK: Problem has no feasible solution".
+The following code leads to an error message which seems to be incorrect (or *at least misleading*...): `MIPSolverException: GLPK: Problem has no feasible solution`.

 - The MILP has a feasible solution, at least the zero vector is feasible.
 - If I set `x.set_max(10^5)` (something smaller than `10^20`), everything works fine. 

[galipnik]

Description changed:

--- 
+++ 
@@ -27,10 +27,18 @@
 sage: for i in srange(14):
 ....:     P.add_constraint(sum(x[j]*A[i][j] for j in srange(20)) == 0)
 sage: P.solve()
+---------------------------------------------------------------------------
+MIPSolverException                        Traceback (most recent call last)
+...
+/.../sage-8.9/local/lib/python2.7/site-packages/sage/numerical/backends/glpk_backend.pyx in sage.numerical.backends.glpk_backend.GLPKBackend.solve (build/cythonized/sage/numerical/backends/glpk_backend.c:9658)()
+   1074             raise MIPSolverException("GLPK: "+solve_status_msg.get(solve_status, "unknown error during call to GLPK : "+str(solve_status)))
+   1075         else:
+-> 1076             raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status)))
+   1077         return 0
+   1078 
+
+MIPSolverException: GLPK: Problem has no feasible solution

-The line of code where the error message comes from is line 1076 in glpk_backend.pyx (observe unknown error during call to GLPK): +(observe unknown error during call to GLPK)

- --> 1076 raise MIPSolverException("GLPK: "+solution_status_msg.get(solution_status, "unknown error during call to GLPK : "+str(solution_status))) -

[galipnik]

Description changed:

--- 
+++ 
@@ -23,7 +23,7 @@
 sage: P = MixedIntegerLinearProgram(maximization=True, solver="GLPK")
 sage: x = P.new_variable(integer=True, nonnegative=True)
 sage: x.set_max(10^25)
-sage: P.set_objective(sum(x[i] for i in srange(25)))
+sage: P.set_objective(sum(x[i] for i in srange(20)))
 sage: for i in srange(14):
 ....:     P.add_constraint(sum(x[j]*A[i][j] for j in srange(20)) == 0)
 sage: P.solve()

[galipnik]

Description changed:

--- 
+++ 
@@ -1,7 +1,7 @@
 The following code leads to an error message which seems to be incorrect (or *at least misleading*...): `MIPSolverException: GLPK: Problem has no feasible solution`.

 - The MILP has a feasible solution, at least the zero vector is feasible.
-- If I set `x.set_max(10^5)` (something smaller than `10^20`), everything works fine. 
+- If I set `x.set_max(10^5)` (something smaller than `10^25`), everything works fine. 

[dcoudert]

comment:5

Same issue with cplex and gurobi. However, with PPL, we get the solution 160000000000000000000000000. I don't know were the problem comes from.

[mkoeppe]

comment:6

Moving tickets to milestone sage-9.2 based on a review of last modification date, branch status, and severity.

[mkoeppe]

comment:8

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mantepse]

comment:13

MIPSolverException: SCIP: Solution is unbounded