4 ms·
If you deal with computationally hard problems, I think there's a whole toolbox of utilities with unbelievable performance, in which millions of PhD-holder-hour
by stncls 5y ago
If you deal with computationally hard problems, I think there's a whole toolbox of utilities with unbelievable performance, in which millions of PhD-holder-hours have been poured, but that get ignored more often than not.
- SAT modeling languages & SAT solvers
- same for SMT (satisfiability modulo theories)
- Constraint programming
- MIP (mixed-integer programming) and its special cases, like
- TSP (traveling salesman problem)
The latter is maybe more anecdotical (as in: fewer direct applications), but it is emblematic of the whole phenomenon. We see a steady stream of claims that NP-hard problems are "impossible" or take "billions of years to solve". We also see blog posts with the latest ML approach "doing the impossible" and providing reasonable (not optimal) solutions to 50-city TSPs. All this while ignoring that with proper maths, we could solve 50-city TSPs to optimality by hand in the fifties, and now Concorde routinely solves 100k-city instances in seconds on an iPhone.
- sidpatil 5y agoMathematical programming (LP, (M)IP, etc.) feel like superpowers to me. Working with them also helped me realize that many optimization problems are actually just closely-related variations of the same problem.
- pdhborges 5y agoMaybe because Linear Programming is P-Complete.
- mw888 5y agoI could certainly read more about this, it sounds fascinating. Will appreciate more of your knowledge or a thoughtful hyper link.
- knodi123 5y agothe concorde reference: https://www.math.uwaterloo.ca/tsp/concorde/DOC/index.html https://www.math.uwaterloo.ca/tsp/concorde/DOC/index.html
- mw888 5y agoI’m aware what the TSP entails and have written algorithms for it myself, but the mathematical approach to programming, so explicitly, is new to me.