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.