Re: Off-by-one error when solving integer linear program

[Heinrich Schuchardt]

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