help-glpk
[Top][All Lists]

## Off-by-one error when solving integer linear program

 From: Matthew Keeter Subject: Off-by-one error when solving integer linear program Date: Tue, 17 Dec 2019 18:12:55 -0500

```Hi folks,

I used GLPK to solve a problem in this year’s Advent of Code , 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 

Strangely, other folks have gotten the correct answer with the same input;
there’s a reddit thread discussing it at .  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?

Regards,
Matt Keeter


 https://gist.github.com/mkeeter/1b4f5a5a89014fdc9e80f43187788436

--------------------------------------------------------------------------------

Maximize out: produced_fuel

Subject to
NZVS: 5 equation1 -29 equation3 -7 equation9 >= 0
ORE: -157 equation1 -165 equation2 -179 equation5 -177 equation6 -165
equation8 +1 consumed_ore >= 0
DCFZ: 6 equation2 -7 equation7 -3 equation9 >= 0
FUEL: 1 equation3 -1 produced_fuel >= 0
XJWVT: -44 equation3 +2 equation7 >= 0
KHKGT: -5 equation3 +8 equation9 >= 0
QDVJ: -1 equation3 +9 equation4 >= 0
GPVTF: -9 equation3 -1 equation4 +2 equation8 >= 0
HKGWZ: -48 equation3 -12 equation4 +5 equation6 -5 equation9 >= 0
PSHF: -8 equation4 +7 equation5 -7 equation7 -10 equation9 >= 0
ore_consumption: consumed_ore <= 1000000000000

Integer
produced_fuel
consumed_ore
equation1
equation2
equation3
equation4
equation5
equation6
equation7
equation8
equation9

end

```