[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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 [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?
Regards,
Matt Keeter
[1] https://adventofcode.com/2019/day/14
[2]
https://www.reddit.com/r/adventofcode/comments/eafj32/2019_day_14_solutions/fawjrgr/
[3] 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
- Off-by-one error when solving integer linear program,
Matthew Keeter <=