Meta-heuristics (SA, GA, PSO, etc) are usually used to solve large problems approximately or near-optimally. However the efficiency of this method is often impractical for real-world projects, even some heuristic rules incorporated, especially for large-scale combinatorial problems.
Is there any methodology or framework able to facilitate solving large NP-hard problems approximately?
Hi:
I think you should be more specific about "large NP-hard real world sproblems". It may happen that a given "big" instance of a problem is easy to solve with a given method, and another one could be hard to solve for the same technique. Take a look at knapsack problems, where specific solvers have been developed over the years.
There is nothing like a "universal solver" able to handle any instance of any optimization problem efficiently.
Hope this answer helps you.
David
Dear Wang,
Yes, you are right meta heuristics approaches consume more time for large problem. Despite such drawback, these methods are using in real world problems. As far as I know, previously some mathematical approaches such as Linear Programming (LP), Non-linear Programming (NLP) were used for solving NP-hard problems, specially for solving optimization problem. Complex and large problem can not be solved easily with these methods, so heuristic approaches came into existence and widely used.
Dear Anupam:
both LP and NLP represents models of the problems. They do not "solve" the problem. For LP you can use the simplex method as the solver, while the situation is not so easy for NLP.
David
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication