Combinatorial Optimization Involving Multiple Objectives: Approximation Algorithms and Applications

这是一个涉及多个目标的组合优化问题的调查。 这样的问题出现在各种应用领域，包括通信网络，非常大规模的集成系统，设施的位置和危险材料的管理。 对于许多这样的问题，即使优化一个目标通常是计算上棘手的。出于这些问题的实际重要性，本研究的重点是开发高效的算法，产生的解决方案，这是接近最优的所有目标。 建议的研究的主要目标包括从不同的应用领域确定多目标优化问题的类别，开发有效的近似算法的问题，并通过分析/实验评估其性能，开发一个软件库的多目标近似算法，可供研究人员和从业人员使用，并深入了解在开发多目标问题的近似算法时遇到的内在困难。 研究生和本科生都将被鼓励参与这项工作。 所取得的成果将纳入研讨会课程适合研究生和高级本科生。一些实际情况要求对限制因素和目标进行认真分析。例如，商业组织可能想要升级互连其分支机构的通信网络，使得可以以更快的速率在分支机构之间交换信息。通常，只有有限的预算可用于升级。本组织希望获得尽可能好的升级，其费用在现有预算范围内。 这种涉及约束和目标的情况出现在许多情况下，包括确定设施（如医院，消防站等）的适当位置。危险材料的管理。在主题上，在这些背景下出现的问题可以表示为涉及多个目标的优化问题。然而，计算这些问题的最佳解决方案往往是不可行的。 本研究的重点是开发程序，可以快速计算的解决方案，接近最佳的解决方案，就所有的目标。 该研究将调查一些应用领域的问题。本研究的目标之一是开发一个软件程序库，可供从业人员和研究人员使用。

This is an investigation of combinatorial optimization problems involving multiple objectives. Such problems arise in a variety of application areas including communication networks, very large scale integrated systems, facility location and management of hazardous materials. For many such problems, even optimizing one objective is often computationally intractable. Motivated by the practical importance of these problems, the focus of this research is on developing efficient algorithms that produce solutions which are near-optimal with respect to all the objectives. The major goals of the proposed research include identifying classes of multiobjective optimization problems from various application areas, developing efficient approximation algorithms for the problems and evaluating their performance through analysis/experimentation, developing a software library of multiobjective approximation algorithms that can be used by researchers and practitioners, and obtaining insights into the intrinsic difficulties encountered in developing approximation algorithms for multiobjective problems. Both graduate and undergraduate students will be encouraged to participate in this work. The results obtained will be incorporated into seminar courses suitable for graduate and advanced undergraduate students. A number of practical situations require a careful analysis of constraints and objectives. For example, a business organization may want to upgrade the communication network interconnecting its branches so that information can be exchanged among the branches at a faster rate. Often, only a limited budget is available for the upgrade. It is of interest to the organization to obtain the best possible upgrade whose cost is within the available budget. Such situations involving constraints and objectives arise in a number of contexts including determining appropriate locations for facilities (such as hospitals, fire stations, etc.) and management of hazardous materials. Ma thematically, the problems arising in these contexts can be expressed as optimization problems involving multiple objectives. However, computing the best solutions to such problems is often infeasible. The focus of this research is on developing procedures that can quickly compute solutions which are close to the best solutions with respect to all the objectives. The research will investigate problems from a number of application areas. One of the goals of this research is to develop a library of software procedures that can be used by both practitioners and researchers.