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.