[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Heinrich Schuchardt
Subject: Re: Off-by-one error when solving integer linear program
Date: Wed, 18 Dec 2019 01:33:08 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0

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 

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

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:

Objective:  out = 82892753 (MAXimum)

KKT.PB: max.abs.err = 1.00e+00 on row 10
        max.rel.err = 1.00e+00 on row 10

So equation PSHF is not fulfilled by the solution GLPK provides.

Best regards


reply via email to

[Prev in Thread] Current Thread [Next in Thread]