Re: Off-by-one error when solving integer linear program
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 >= -1 equation9 >= -51808000 equation8 >= -377623000 equation7 >= -182364 equation6 >= -869683000 equation5 >= -190818 equation4 >= -9210310 equation3 >= -82892800 equation2 >= -215348 equation1 >= -553309000 integer produced_fuel consumed_ore equation9 equation8 equation7 equation6 equation5 equation4 equation3 equation2 equation1 end -- Michael henne...@web.cs.ndsu.nodak.edu "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
Re: Off-by-one error when solving integer linear program
This is the first of the larger example problems. The constraints are derived from this set of "chemical reactions": 157 ORE => 5 NZVS 165 ORE => 6 DCFZ 44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL 12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ 179 ORE => 7 PSHF 177 ORE => 5 HKGWZ 7 DCFZ, 7 PSHF => 2 XJWVT 165 ORE => 2 GPVTF 3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT -Matt > On Dec 19, 2019, at 3:45 AM, Michael Hennebry > wrote: > > On Wed, 18 Dec 2019, Matthew Keeter wrote: > >> Ah, I just realized that you only see Part 2 if you're logged in and have >> solved Part 1. >> >> The goal of Part 2 is to maximize production of the FUEL element, starting >> with 1 trillion >> units of ORE; that's the problem that I'm solving in my LP file. > > That helps some. > I'm seeing the 1 trillion now. > Where is the other data? > >> Since each reaction occurs an integer number of times (and both consumes and >> produces an integer number of reagents / products), the answer should be an >> integer. > > 82,892,753.14 was a joke, son. > > -- > Michael henne...@web.cs.ndsu.nodak.edu > "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
Re: Off-by-one error when solving integer linear program
On Wed, 18 Dec 2019, Matthew Keeter wrote: Ah, I just realized that you only see Part 2 if you're logged in and have solved Part 1. The goal of Part 2 is to maximize production of the FUEL element, starting with 1 trillion units of ORE; that's the problem that I'm solving in my LP file. That helps some. I'm seeing the 1 trillion now. Where is the other data? Since each reaction occurs an integer number of times (and both consumes and produces an integer number of reagents / products), the answer should be an integer. 82,892,753.14 was a joke, son. -- Michael henne...@web.cs.ndsu.nodak.edu "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
Re: Off-by-one error when solving integer linear program
Ah, I just realized that you only see Part 2 if you're logged in and have solved Part 1. The goal of Part 2 is to maximize production of the FUEL element, starting with 1 trillion units of ORE; that's the problem that I'm solving in my LP file. Since each reaction occurs an integer number of times (and both consumes and produces an integer number of reagents / products), the answer should be an integer. -Matt On Tue, Dec 17, 2019 at 11:40 PM Michael Hennebry < henne...@web.cs.ndsu.nodak.edu> 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. > > I'm really confused about what problem is being solved. > The given ILP does not resemble the problem of producing one unit of fuel. > For the puzzle data I found, one would have 59 variables (columns), > one for each reaction. > I saw mention of more than one part, > so I expect I am missing something. > > > 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. > > The correct answer is 82,892,753.14 . > > -- > Michael henne...@web.cs.ndsu.nodak.edu > "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 >
Re: Off-by-one error when solving integer linear program
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. I'm really confused about what problem is being solved. The given ILP does not resemble the problem of producing one unit of fuel. For the puzzle data I found, one would have 59 variables (columns), one for each reaction. I saw mention of more than one part, so I expect I am missing something. 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. The correct answer is 82,892,753.14 . -- Michael henne...@web.cs.ndsu.nodak.edu "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
Re: Off-by-one error when solving integer linear program
On Tue, 17 Dec 2019, Michael Hennebry wrote: What problem are you trying to solve? If it's not this one: 71 ORE => 8 CNZTR Oops. Should have benn 171 ORE Now I get 2,210,736 which I now see is the value listed above the example I mistook for puzzle data. I infer that "To play" includes getting a look puzzle data. I have a python script that turns the puzzle data into glpsol --lp data. It works for examples. For the puzzle data, I get 399063 . Where are you getting your correct value? -- Michael henne...@web.cs.ndsu.nodak.edu "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
Re: Off-by-one error when solving integer linear program
What problem are you trying to solve? If it's not this one: 71 ORE => 8 CNZTR 7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL 114 ORE => 4 BHXH 14 VRPVC => 6 BMBT 6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL 6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT 15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW 13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW 5 BMBT => 4 WPTQ 189 ORE => 9 KTJDG 1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP 12 VRPVC, 27 CNZTR => 2 XDBXC 15 KTJDG, 12 BHXH => 5 XCVML 3 BHXH, 2 VRPVC => 7 MZWV 121 ORE => 7 VRPVC 7 XCVML => 6 RJRHP 5 BHXH, 4 VRPVC => 5 LTCX what problem is it? I get 1,341,336 from ILP with GLPK. One variable for each of 17 reactions. I have no idea why you would need an explicit bound on ORE consumption. A trillion seems a bit excessive. From where are you getting your correct answer? -- Michael henne...@web.cs.ndsu.nodak.edu "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
Re: Off-by-one error when solving integer linear program
Interesting – running on my computer, the results file doesn't mention any errors or infeasibility (but it’s also returning a different result for the objective). Here’s what I see: Rows: 11 Columns:11 (11 integer, 0 binary) Non-zeros: 32 Status: INTEGER OPTIMAL Objective: out = 82892752 (MAXimum) [...] Integer feasibility conditions: KKT.PE: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality > On Dec 17, 2019, at 7:33 PM, Heinrich Schuchardt wrote: > > On 12/18/19 12:12 AM, Matthew Keeter wrote: >> 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? > > There are several tolerances taken into account by GLPK including > tol_int defaulting to 1e-5. If a problem is ill-conditioned, you may get > errors due to these tolerances. > > Looking at your ore_consumption constraint you are looking for a > solution that is exact to a factor of 1 in 177 trillions. This is > nothing GLPK can deliver. > > When running your problem with > > ./glpsol --lp ore.lp -o result > > I get in file result: > > Status: INTEGER OPTIMAL > Objective: out = 82892753 (MAXimum) > > KKT.PB: max.abs.err = 1.00e+00 on row 10 >max.rel.err = 1.00e+00 on row 10 >SOLUTION IS INFEASIBLE > > So equation PSHF is not fulfilled by the solution GLPK provides. > > Best regards > > Heinrich
Re: Off-by-one error when solving integer linear program
On 12/18/19 12:12 AM, Matthew Keeter wrote: 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? There are several tolerances taken into account by GLPK including tol_int defaulting to 1e-5. If a problem is ill-conditioned, you may get errors due to these tolerances. Looking at your ore_consumption constraint you are looking for a solution that is exact to a factor of 1 in 177 trillions. This is nothing GLPK can deliver. When running your problem with ./glpsol --lp ore.lp -o result I get in file result: Status: INTEGER OPTIMAL Objective: out = 82892753 (MAXimum) KKT.PB: max.abs.err = 1.00e+00 on row 10 max.rel.err = 1.00e+00 on row 10 SOLUTION IS INFEASIBLE So equation PSHF is not fulfilled by the solution GLPK provides. Best regards Heinrich
Off-by-one error when solving integer linear program
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 <= 1 Integer produced_fuel consumed_ore equation1 equation2 equation3 equation4 equation5 equation6 equation7 equation8 equation9 end
