ITR/SY: Stochastic Combinatorial Optimization

点击翻译按钮获取中文摘要

Optimization is the science that integrates information into a mathematical model whose solution yields optimal decisions. It has developed into a scientific discipline with useful applications, which are routinely used in industry. However, there are many real optimization problems for which solutions are not known. For example, suppose a snowstorm is approaching Chicago. At its operations center, an airline is reacting by making plans to cancel and reroute flights. Substantial information on weather forecasts, plane and crew status, passenger itineraries, and hotels is available to make an optimal plan. However, this information is typically not exploited to its fullest extent. Why is this the case, especially as the airline is a very sophisticated user of optimization for planning? Because the application is a large-scale stochastic combinatorial optimization problem for which there is no known algorithm producing good solutions in reasonable time.This project aims to carry out fundamental research in this relatively new area of science to obtain good solutions to these problems. It will investigate two complementary areas: (1) the integration of constraint and integer programming that provide orthogonal strengths in approaching stochastic combinatorial optimization problems; and (2) stochastic substructures to design efficient solutions or approximations for typical instances. This research will advance our knowledge about large-scale stochastic combinatorial optimization problems and allow for their solutions to be used in complex and critical operations.