Applying Methods from Combinatorial Optimization in Solving Large-Scale Real World Problems

点击翻译按钮获取中文摘要

Many practically important optimization problems are combinatorial in nature. Some examples include the minimum cost design of reliable communication networks, fast printed circuit board production, the building of genetic evolutionary trees as well as the optimization of various scheduling and routing problems. Unfortunately, may such problems belong to a class called "NP-hard", which is considered strong evidence that they are extremely difficult to solve, and that it is highly unlikely that we will find techniques for solving them that are guarantee to be practical and efficient in all cases. The lack of efficient methods for such problems is of significant importance as there exist large-scale, real world instances requiring solutions. Fortunately, in practice, it is often sufficient to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal (best) solution, which in many cases is much more viable task.