[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Off-by-one error when solving integer linear program
From: |
Michael Hennebry |
Subject: |
Re: Off-by-one error when solving integer linear program |
Date: |
Thu, 19 Dec 2019 14:36:55 -0600 (CST) |
User-agent: |
Alpine 2.20 (DEB 67 2015-01-07) |
On Tue, 17 Dec 2019, Michael Hennebry wrote:
On Tue, 17 Dec 2019, Matthew Keeter wrote:
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.
As noted elsewhere, an upper bound of a trillion
requires more precision than GLPK will normally require.
I do not get an integer objective.
The correct answer is 82892753, and I?m getting 82892752.
The correct answer is 82,892,753.14 .
From a two-step process, I get 82,892,800-47=82,892,753 unit of fuel
from 1,000,000,000,000-99=999,999,999,901 units of ore.
For the second step, I solved for differences with the first step solution.
The RHSs ranged from -17,520 to 24,000.
None of the structural variables were at their bounds.
aximize out: produced_fuel
Subject to
NZVS: 5 equation1 -29 equation3 -7 equation9 >= 2200
ORE: -157 equation1 -165 equation2 -179 equation5 -177 equation6 -165 equation8 +1
consumed_ore >= -381000
DCFZ: 6 equation2 -7 equation7 -3 equation9 >= 24000
FUEL: 1 equation3 -1 produced_fuel >= 0
XJWVT: -44 equation3 +2 equation7 >= 3200
KHKGT: -5 equation3 +8 equation9 >= 0
QDVJ: -1 equation3 +9 equation4 >= 10
GPVTF: -9 equation3 -1 equation4 +2 equation8 >= -490
HKGWZ: -48 equation3 -12 equation4 +5 equation6 -5 equation9 >= 3120
PSHF: -8 equation4 +7 equation5 -7 equation7 -10 equation9 >= -17520
ore_consumption: 1 consumed_ore <= 0
bounds
produced_fuel >= -82892800
consumed_ore >= -1000000000000
equation9 >= -51808000
equation8 >= -377623000
equation7 >= -1823640000
equation6 >= -869683000
equation5 >= -1908180000
equation4 >= -9210310
equation3 >= -82892800
equation2 >= -2153480000
equation1 >= -553309000
integer
produced_fuel
consumed_ore
equation9
equation8
equation7
equation6
equation5
equation4
equation3
equation2
equation1
end
--
Michael address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
-- someeecards