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