Discrete Optimization: From Applications to Relaxations

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

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?*** **