4 ms·
I totally agree with this, both the part about having to be clever with the model implementation and how fast and usable it is. For my own research, it ended up
by JZL003 4y ago
I totally agree with this, both the part about having to be clever with the model implementation and how fast and usable it is. For my own research, it ended up that it was a type of set cover problem. To me it felt large, ended up with almost a million non-zero values to optimize (and had to do 10k of them), but the state of the art is so fast. CPLEX optimizes them in like 3 seconds and can tell me that it's provably optimal. Even open source solvers (HiGHS) solves in like 10 seconds
It is true that when I phrased the problem wrong (with multiplication not addition), it was taking forever, and I had to mess around a long time to figure it out. ChatGPT actually sorta helped a little
But it does feel like magic and not used enough. I think Julia JuMP goes a long way towards just expressing the problem easily. It might take more work/tricks to get it to work (big-M tricks are crazy to me) but at least as a first pass if it just works is worth a try, I think
And to be fair, I really wanted it to be provably optimal for the fun of it. But when I set even a 10 minute timelimit, it got a really good solution across the board much faster than I could have found with manual programming
- JZL003 4y agoAlso like O(N^2) is surprisingly doable even for very big N. Maybe I shouldn't have been surprised, but another problem was N^2 for a pretty big N (100k) with a dynamic programming. I was worried it would never finish But making a 100k by 100k matrix in julia really isn't so bad (and can use memoization), just rent a big machine on GCP for an hour or two, and it chewed through it fast
- kadoban 4y agoCompetitive programming gives you some good intuition on these types of things. N of around 100000 is where you stop looking for O(n^2) algorithms, but the key there is you only have single-digit-seconds for your solution to run. Which is just to say: yeah, machines can chew through _a lot_ of crap, especially if it's not something a user has to wait for and you can do it over-night or something.