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

[Michael Hennebry]

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