Title

Metaheuristic applications and their solutions quality

Abstract/Description

Over the past few decades, a wide variety of classes of combinatorial problems (e.g. the assignment problem, the knapsack problem, the vehicle routing problem, etc.) have emerged - from such areas as management science, telecommunication, AI, VLSI design and many others. Many large combinatorial problems are NP-hard problems because of the combinatorial growth of their solution search space with the problem size. Such problems are commonly solved by some version of a prominent metaheuristic (e.g. Genetic Algorithms, Tabu Search, Simulated Annealing and etc.). These heuristics seek good but approximate solutions at a reasonable computational cost. These heuristics are of stochastic nature. Heuristic researchers often make claims about the relative performance of metaheuristics without considering their stochastic nature and consequently their claims are not reliable. This paper discusses how to make an effective application of these metaheuristics to any NP-hard problem and to assess their solution quality in an acceptable way.

Location

Crystal Ball Room A, Hotel Pearl Continental, Karachi, Pakistan

Session Theme

Algorithms, Tools and Applications [ALGO-2]

Session Type

Other

Session Chair

Dr. Ashraf Iqbal

Start Date

27-8-2005 5:05 PM

End Date

27-8-2005 5:30 PM

Share

COinS
 
Aug 27th, 5:05 PM Aug 27th, 5:30 PM

Metaheuristic applications and their solutions quality

Crystal Ball Room A, Hotel Pearl Continental, Karachi, Pakistan

Over the past few decades, a wide variety of classes of combinatorial problems (e.g. the assignment problem, the knapsack problem, the vehicle routing problem, etc.) have emerged - from such areas as management science, telecommunication, AI, VLSI design and many others. Many large combinatorial problems are NP-hard problems because of the combinatorial growth of their solution search space with the problem size. Such problems are commonly solved by some version of a prominent metaheuristic (e.g. Genetic Algorithms, Tabu Search, Simulated Annealing and etc.). These heuristics seek good but approximate solutions at a reasonable computational cost. These heuristics are of stochastic nature. Heuristic researchers often make claims about the relative performance of metaheuristics without considering their stochastic nature and consequently their claims are not reliable. This paper discusses how to make an effective application of these metaheuristics to any NP-hard problem and to assess their solution quality in an acceptable way.