[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-glpk] GLPK reports wrong solution for MIP

From: Andrew Makhorin
Subject: Re: [Bug-glpk] GLPK reports wrong solution for MIP
Date: Thu, 13 Sep 2007 09:16:18 +0400

> for the attached model, GLPK 4.21 gives me a wrong solution.
> CPLEX and CBC report 218.512850, but GLPK gives 197.55, and it's a 
> minimization problem.
> Fixing the variables to the reported integer solution and running GLPK
> on the resulting LP reports an infeasible problem (what is correct).

> Maybe its a similar problem as reported last weak on the bug-glpk list,
> since the model is actually very bad scaled.

Thank you for your report.

In fact, the wrong result appears due to badly scaled constraint matrix,
namely, due to the following "big M" constraints:

 R0000273: + C0000187 - 10000000000000 C0000369 <= 0
 R0000274: + C0000188 - 10000000000000 C0000370 <= 0
 R0000275: + C0000189 - 10000000000000 C0000371 <= 0
 . . .

where C0000187, C0000188, C0000189, ... are non-negative variables, and
C0000369, C0000370, C0000371, ... are binary variables.

Probably cplex and cbc reduce such big coefficients, however, glpk does
not reduce them that leads to excessive round-off errors.

You can use the api routines lpx_check_kkt and lpx_check_int to check
that the solution reported by the glpk solver is correct.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]