Mathematical Sciences: Computational and Mathematical Investigations in 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.