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
