Applying Methods from Combinatorial Optimization in Solving Real World Problems

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

Many practically important problems are combinatorial in nature. Some examples of such problems include the design of reliable communication networks, fast printed circuit board production, scheduling problems and routing problems. Many such problems are known to belong to a class called "NP-hard", which is strong evidence that these problems are extremely difficult to solve, and that it is unlikely that efficient techniques for finding the optimal (i.e. the best) solution exist. The lack of efficient methods for such problems is of real importance as there exist large scale, real world instances requiring solutions. Fortunately, in practice, it is often satisfactory to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal solution.