Mathematical Sciences: Computational and Mathematical Investigations in Optimization

数学科学：优化中的计算和数学研究

• 批准号: 9505155
• 金额: $ 49.2万
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1998-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9505155&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Computational; Investigations; Optimization

Todd The investigator and his colleagues undertake broad studies of optimization algorithms and the mathematical theory underlying them. The project covers continuous and discrete optimization algorithms, both exact and approximate, their computational complexity, practical large-scale implementation, performance guarantees (in the case of approximate algorithms), and applications in the physical sciences such as elementary particle tracking, as well as more conventional applications in manufacturing and logistics. Particular projects include: - a continuation of large-scale computational testing of implementations of minimum-cost network flow algorithms; - development and testing of algorithms for large-scale nonlinear minimization problems with bound constraints; - performance guarantees for efficient approximation algorithms for machine-scheduling problems with budget constraints and for other combinatorial optimization problems; - development of more efficient interior-point methods for convex programming and for linear programming problems where no initial interior feasible solution is known; - studies of the polyhedral structure of combinatorial problems in graph theory and partially ordered sets, as well as in applications such as crew scheduling -- computational implementation and testing have been an integral aspect of these studies; and - further development of complexity theory for continuous nonconvex problems. These projects range from modeling through algorithm development and analysis to implementation and testing. Optimization addresses questions like: - How do you schedule the production of hundreds of items with varying demands over several months to minimize setup and holding costs, subject to resource limitations and capacities? - How do you determine the geometric conformation of a protein (how it ``folds") given an approximate en ergy functional for any position? Indeed, complex systems arising in the engineering, physical, and biological sciences, and in the manufacturing and service industries, involving hundreds to millions of interacting variables, frequently lead to optimization problems when one wishes to control or predict their behavior. The investigators study a number of specific projects related to modeling and algorithm development for a variety of applications, ranging from traditional settings like resource allocation, planning, logistics, and distribution problems to new application areas such as airline crew-scheduling, elementary particle tracking, and shop scheduling. A common thread is the search for efficient methods to solve exactly large-scale instances of such problems, or, if that is not likely to be possible, for efficient algorithms that are guaranteed to obtain a solution that is close to optimal in a precise sense. The investigators also test these algorithms computationally on representative instances of such problems using serial and parallel computers.

托德 研究者和他的同事们对优化算法及其数学理论进行了广泛的研究。 该项目涵盖了连续和离散优化算法，包括精确和近似，其计算复杂性，实际大规模实施，性能保证（在近似算法的情况下），以及在物理科学中的应用，如基本粒子跟踪，以及在制造和物流中的更传统的应用。 具体项目包括： - 继续进行大规模的计算测试， 最小成本网络流算法的实现; - 开发和测试大规模的算法 有界约束的非线性极小化问题; - 有效逼近的性能保证 有预算机器排序问题的算法 约束和其他组合优化问题; - 制定更有效的通道点方法， 凸规划和线性规划问题 其中初始内部可行解未知; - 多面体结构的研究 图论和偏序集的问题，以及 例如在机组调度等应用中， 实施和测试一直是 这些研究;以及 - 复杂性理论的进一步发展 非凸问题 这些项目的范围从建模到算法开发和分析，再到实施和测试。 优化解决了以下问题： - 您如何安排数百种产品的生产， 在几个月内改变需求，以最大限度地减少设置， 在资源有限的情况下， 能力？ - 如何确定蛋白质的几何构象 (how它"折叠”）给出一个近似的能量函数， 任何位置？ 事实上，工程、物理和生物科学以及制造业和服务业中出现的复杂系统，涉及数百万个相互作用的变量，当人们希望控制或预测其行为时，经常会导致优化问题。 研究人员研究了许多与各种应用的建模和算法开发相关的具体项目，从传统的资源分配，规划，物流和配送问题到新的应用领域，如航空公司机组人员调度，基本粒子跟踪和车间调度。 一个共同的思路是寻找有效的方法来解决这些问题的大规模实例，或者，如果这是不可能的，有效的算法，保证获得一个解决方案，在精确的意义上接近最优。 调查人员还测试这些算法计算上的代表性实例，这些问题使用串行和并行计算机。