ITR/SY: Stochastic Combinatorial Optimization

优化是一门将信息整合到数学模型中的科学，其解决方案可以产生最佳决策。 它已经发展成为一门具有实用应用的科学学科，在工业中经常使用。 然而，有许多真实的优化问题的解决方案是未知的。例如，假设一场暴风雪正在接近芝加哥。 在其运营中心，一家航空公司正在做出反应，计划取消和改变航班。 有关天气预报、飞机和机组人员状况、乘客行程和酒店的大量信息可用于制定最佳计划。 然而，这些信息通常没有得到最充分的利用。 为什么会出现这种情况，特别是航空公司是一个非常复杂的优化规划用户？ 由于该应用程序是一个大规模的随机组合优化问题，没有已知的算法在合理的时间内产生良好的解决方案。本项目旨在在这一相对较新的科学领域进行基础研究，以获得这些问题的良好解决方案。 它将研究两个互补的领域：（1）约束和整数规划的整合，提供正交的力量，在接近随机组合优化问题;和（2）随机子结构，设计有效的解决方案或近似的典型实例。 这项研究将推进我们对大规模随机组合优化问题的认识，并允许其解决方案用于复杂和关键的操作。

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.