Discrete Optimization: From Applications to Relaxations

点击翻译按钮获取中文摘要

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?