Discrete Optimization: From Applications to Relaxations

这是一个关于优化的研究建议，这个领域跨越了几个学科：纯数学和应用数学，计算机科学，运筹学和工程学。数学优化之所以蓬勃发展，部分原因在于它的大量应用。除了库存管理和调度等传统的物流出口外，新的应用对优化方法提出了要求，以科普非常大规模的数据集和对实时答案的需求。其他应用程序寻求新的模式，将博弈论的战略到优化器的目标。 例如，几乎所有的在线零售商都在其运营的各个方面（履行，运输，收入管理）利用优化工具。相应地，该领域也需要新的人才，以满足人们对机器学习、分析和数据科学专业知识似乎永不满足的需求，这些领域都是离散和连续优化的强大用户。建议的研究方向范围从纯粹的理论和结构性的整数规划的建模和实证问题，以及在数据网络的实际考虑动机。相当大的重点放在进一步发展的鲁棒优化，一种方法来处理优化下的不确定性。PI最近也在在线算法中工作，这可以被视为处理不确定性的另一种模型。该提案中反复出现的一个论点是，当利用基本理论原理时，利用优化的力量解决现实问题的效果会得到改善。 因此，除了提出几个计算活动，一些具有挑战性的中期/长期的理论目标被确定。这些问题包括关于流割间隙和稀疏割的数学问题，例如何时有限度量可嵌入L_1且具有常数失真？什么时候平行六面体中的所有格点都位于超平面上？* **

This is  a research proposal on optimization, an area which crosses several disciplines: pure and applied mathematics, computer science, operations research and engineering. Mathematical optimization is thriving in part due to a wealth of applications. In addition to traditional logistic outlets such as inventory management and scheduling, new applications put demands on optimization methodology to cope with very large scale data sets and the desire for real-time answers. Additional applications seek new models which incorporate game-theoretic strategy into the optimizer's objective. Virtually all online retailers, for instance, are leveraging optimization tools in various aspects of their operations (fulfilment, shipping, revenue management). There is a corresponding demand for new personnel in the area to meet a seemingly insatiable appetite for expertise in machine learning, analytics and data science, areas which are strong users of discrete and continuous optimization.***Research directions proposed range from purely theoretical and structural topics in integer programming to modelling and empirical questions well-motivated by practical considerations in data networks. Considerable emphasis is placed on further development of robust optimization, one approach for  coping with optimization under uncertainty. The PI has also recently worked in online algorithms, which can be viewed as another model dealing with uncertainty. A recurring argument in the proposal is that harnessing the power of optimization for real-world problems is improved when it is informed by the underlying theoretical principles.  Thus, apart from presenting several computational activities, a number of  challenging medium/long-term  theoretical objectives are identified. These include mathematical questions about flow-cut gaps and sparsest cut, such as when is a finite metric embeddable into L_1 with constant distortion?, to when do all lattice points in a parallelepiped lie on a hyperplane?*** **