help-glpk
[Top][All Lists]

## 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 , 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

--