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.