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.
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/
What can I do to speed up further? Is reformulation as MILP even the right choice for this problem?
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.
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?
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.)
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.
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).
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.