2 ms·
You are technically correct. To interpret the observation a bit more meaningfully: It's surprising how many problems can be formulated as continuous (!) linea
by eru 3y ago
You are technically correct.
To interpret the observation a bit more meaningfully:
It's surprising how many problems can be formulated as continuous (!) linear optimisation.
And it is surprising how many problems can be formulated somewhat naturally as mixed-integer linear optimisation. And 'many of them can be solved or well-approximated quickly', exactly as you say.
---
I seem to remember that continuous linear optimisation is to P what integer linear optimisation is to NP. In the sense that there's some natural reduction of many problems in P to continuous linear optimisation.
(I don't remember if that's just an informal observation, or whether there's some formal way to reduce problems in P in eg linear time to linear optimisation? https://en.wikipedia.org/wiki/P-complete#P-complete_problems https://en.wikipedia.org/wiki/P-complete#P-complete_problems mentions Linear Optimisation as being P-complete, but I haven't vetted all the fine-print, eg about what specific reduction they are using.)