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.