|
| From: | Michael Hennebry |
| Subject: | Re: [Help-glpk] glpsol, arbitrary precision and large numbers |
| Date: | Sat, 30 Jun 2012 14:20:09 -0500 (CDT) |
| User-agent: | Alpine 1.00 (DEB 882 2007-12-20) |
On Fri, 29 Jun 2012, Andrew Makhorin wrote:
When this is solved (with --exact --noscale), glpsol tells me "INTEGER OPTIMAL SOLUTION FOUND" and the variable assignments in the solution are as follows: No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 18 dcsn_lte_0 * 0 0 1 35 u_EAX_4008e0 9 0 4.29497e+09 and the row solution: No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 15 c13 9 4 If we plug the assignment into the original constraint, then we get: -4294967296 * 0 + 1 * 9 <= 4 therefore: 9 <= 4 Which is false, so under this assignment the system in infeasible. The solver should have either tried a different assignment of either variables, or if it could not, then it should have reported the problem infeasible? Right?
Is this a bug, a misuse of glpk or a misunderstanding?Being numerical procedures both the glpk integer optimizer and underlying simplex solver work with a finite relative precision, and you should not expect that the simplex solver is able to obtain an exact solution even if your input data are integral (i.e. free of round-off errors). In other word, the constraint actually used on obtaining basic solutions is the following:
I thought that that was the point of --exact. Even if the input routines are double precision, the given numbers are representable. Perhaps there is a presolve that is not done with exact arithmetic. -- Michael address@hidden "On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to run with scissors, that my fiance ran me through with a broadsword." -- Lily
| [Prev in Thread] | Current Thread | [Next in Thread] |