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

Interesting – running on my computer, the results file doesn't mention any
errors or infeasibility (but it’s also returning a different result for the objective).

Here’s what I see:

Rows:       11
Columns:    11 (11 integer, 0 binary)
Non-zeros:  32
Status:     INTEGER OPTIMAL
Objective:  out = 82892752 (MAXimum)

[...]

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

> On Dec 17, 2019, at 7:33 PM, Heinrich Schuchardt <[email protected]> wrote:
> 
> 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