4 ms·
It was a response to > It's surprising how many problems can be formulated as linear optimization. i.e., all problems in NP (which is most problems you're lik
by tylerhou 3y ago
It was a response to
> It's surprising how many problems can be formulated as linear optimization.
i.e., all problems in NP (which is most problems you're likely to encounter on a day-to-day basis) can be solved with ILP, and many of them can be solved or well-approximated quickly.
- eru 3y agoYou 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.)