3 ms·
Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.
by Mr_P 10y ago
Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.
- nhaehnle 10y agoIf you can transform your NP hard optimization problem into an LP, you have proven P = NP because LPs can be solved in polynomial time. That said, many combinatorial optimization problems that look quite similar to NP hard problems have very nice and efficient LP formulations, and for many NP hard problems, integer programming-based methods (which in the end mostly solve LP relaxations) are among the best algorithms. For example, planar TSP can be solved for tens or even hundreds of thousands of nodes using the LP relaxation, branch, and cut tool set. Modern LP solvers don't just use the Simplex method though. I'm very partial to the Simplex method myself, but in practice, Interior Point Methods are often used.
- 110011 10y agoAdding to what you say, OP might have meant the use of LP solvers in branch and bound type algorithms to solve hard problems after recasting them as integer programs.