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

[Matthew Keeter]

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 <address@hidden> 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