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.