On 12/18/19 12:12 AM, Matthew Keeter wrote:
Hi folks,
I used GLPK to solve a problem in this year’s Advent of Code [1], and noticed
that it produces a very slightly wrong answer for one of the examples.
It’s an integer linear programming problem, pasted below the fold in CPLEX LP
format.
The correct answer is 82892753, and I’m getting 82892752.
I’ve pasted my glpsol output at [2]
Strangely, other folks have gotten the correct answer with the same input;
there’s a reddit thread discussing it at [1]. I'm on a Mac OS 10.13.6,
GLPK 4.65, GMP 6.1.2, compiled with Apple LLVM version 10.0.0
(clang-1000.11.45.5)
Any ideas?
There are several tolerances taken into account by GLPK including
tol_int defaulting to 1e-5. If a problem is ill-conditioned, you may get
errors due to these tolerances.
Looking at your ore_consumption constraint you are looking for a
solution that is exact to a factor of 1 in 177 trillions. This is
nothing GLPK can deliver.
When running your problem with
./glpsol --lp ore.lp -o result
I get in file result:
Status: INTEGER OPTIMAL
Objective: out = 82892753 (MAXimum)
KKT.PB: max.abs.err = 1.00e+00 on row 10
max.rel.err = 1.00e+00 on row 10
SOLUTION IS INFEASIBLE
So equation PSHF is not fulfilled by the solution GLPK provides.
Best regards
Heinrich
