# Even Gurobi is too slow for my Minecraft problem

**URL:** <https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231>\
**Category:** Optimization (Mathematical)\
**Created:** [September 9, 2024, 11:59pm UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231 "2024-09-09T23:59:43Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 9, 2024, 11:59pm UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/1 "2024-09-09T23:59:43Z")

</div>

Recently, I made a reactor designer for Minecraft Nuclearcraft. I even obtained a Gurobi license for it. Then, I tuned lots of parameters. I decided to tune up the cuts that happened a lot to be aggressive and I used the interior point method, which is faster for this case. I also tuned the tolerance.

The goal is to maximize the energy (rf/t) generated.

> <https://github.com/AliceRoselia/Nuclearcraft_optimization/blob/main/Nuclearcraft_Gurobi.jl>

For reference, here is the requirement of the reactor. [Fission Reactor - Official Feed The Beast Wiki](https://ftb.fandom.com/wiki/Fission_Reactor)

However, after a lot of tuning and so on, this is still slow, especially on larger reactor sizes.  
Compare this to programs like this, running on JavaScript and probably on a single core.  
[https://leu-235.com/](https://leu-235.com/)

What can I do to speed up further? Is reformulation as MILP even the right choice for this problem?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 10, 2024, 3:15am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/2 "2024-09-10T03:15:54Z")

</div>

I don’t know if we’ll be much help for this model. This looks like a very large and non-trivial MIP with some very convoluted constraints. (Didn’t you make a post about this a few days ago? I thought it was in the Optimization section, but I can’t see it now. I didn’t get a chance to reply.)

You shouldn’t expect Gurobi to solve this problem without a bit of care and thought in the formulation. MIPs are NP-hard to solve! It’s more of a surprise that we can sometimes solve MIPs in a reasonable time, instead of being able to solve large arbitrary MIPs in general.

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 10, 2024, 4:24am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/3 "2024-09-10T04:24:09Z")

</div>

> [@odow](#):
>
> MIPs are NP-hard to solve!

I know MIPs are NP-hard **in general.** However, I was hoping that this MIP would fall into the easy case. This was because this MIP was based on a silly problem humans are able to do quite well. I thought battle-tested Gurobi would be able to solve it quite quickly. NP-hardness only suggests that the problem is hard to solve in the worst case. Sudoku is also an NP-hard problem, yet my solver is able to solve any problem I threw at it easily. As far as I’ve heard, it’s not uncommon to see a problem being NP-hard yet commonly solved in practice. I thought my problem would be an easy case, but the experiment showed it wrong. @odow Do you know how you can know if an MIP problem would fall into the easy case? Or is it just trying it out?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 10, 2024, 4:43am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/4 "2024-09-10T04:43:13Z")

</div>

> Do you know how you can know if an MIP problem would fall into the easy case? Or is it just trying it out?

Just trying it out.

Your formulation is very large and convoluted, so there might be a better way to write it. A better claim is: Gurobi struggles to solve the model you have written. There might be a different formulation that is easier to solve. (But I don’t have any good ideas to start with because I don’t really understand your model based on the code.)

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 10, 2024, 5:07am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/5 "2024-09-10T05:07:33Z")

</div>

> [@odow](#):
>
> Your formulation is very large and convoluted, so there might be a better way to write it.

I tried to write it out as straightforwardly as possible, but the original problem was really complicated. It took an entire wiki page just to explain the mechanics.

The problem I had was probably with the reactor boosting. Basically, each reactor cell can be boosted from six directions. When boosted, the energy increases linearly per the boosting direction, but the heat increases roughly quadratically. The problem is that if the blocks are separated by at most **four** moderator blocks, they’re still considered boosting each other. I used lots of variables and lots of constraints in formulating the boosting condition. Is there a simpler way to formulate the boosting constraint? If that could be out of the way, maybe Gurobi could solve it.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [September 10, 2024, 5:20am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/6 "2024-09-10T05:20:57Z")

</div>

I don’t know anything about optimization, so my observation might be useless. This problem has symmetry, right? You can rotate the arrangement and the output is identical. Does that generally make the optimization harder for the solver? Is there a way to reduce the problem space by removing the symmetry? Maybe you could try to find a completely symmetric solution since that would reduce the number of variables by a factor of ~16 (rotations and reflections of the cube).

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 10, 2024, 5:22am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/7 "2024-09-10T05:22:35Z")

</div>

Even HiGHS have symmetry detection iirc. Perhaps Gurobi already took advantage of this fact. Needless to say, if it did, this was not sufficient.

---

<div class="post-metadata">

**Author:** ![ufechner7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ufechner7/32/51363_2.png) [@ufechner7](https://discourse.julialang.org/u/ufechner7)\
**Post date:** [September 10, 2024, 6:27am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/8 "2024-09-10T06:27:37Z")

</div>

> [@odow](#):
>
> MIPs are NP-hard to solve!

What are MIPs?

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 10, 2024, 6:36am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/9 "2024-09-10T06:36:39Z")

</div>

Mixed integer programming, or linear programming where there are some extra constraints that some variables must be integers.

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 11, 2024, 3:56pm UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/10 "2024-09-11T15:56:39Z")

</div>

I refactored the code to use less variables and less integer variables, and the result is… it gets slower!

I don’t understand why!

> <https://github.com/AliceRoselia/Nuclearcraft_optimization/blob/main/Nuclearcraft_refactor.jl>

And then I made a version that marked implied integers as integers, and it performed better for some reasons.

> <https://github.com/AliceRoselia/Nuclearcraft_optimization/blob/main/Nuclearcraft_implied_ints_as_ints.jl>

---

<div class="post-metadata">

**Author:** ![Tarny\_GG\_Channie](https://avatars.discourse-cdn.com/v4/letter/t/3bc359/32.png) [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)\
**Post date:** [September 12, 2024, 10:28am UTC](https://discourse.julialang.org/t/even-gurobi-is-too-slow-for-my-minecraft-problem/119231/11 "2024-09-12T10:28:15Z")

</div>

Update, it looks like not locking implied integers as integers would be faster than otherwise in larger reactors, which is where it’s relevant. The Gurobi optimizer kinda can compete with the leu-235.