Eager: Discrete Optimization Algorithms for 21st Century Algorithms

离散优化问题已经被优化和计算机科学界研究过了。这个EAGER项目建议通过计算机科学家和数学和工程优化专家之间的跨学科合作，综合两个社区的想法，开发新的方法。目标是通过结合整数规划的见解和最先进的方法（例如，切割平面和分支定界）和计算机科学的算法思想（包括在线算法和机器学习）。为了能够在真实世界的实例上评估和比较方法，PI计划开发一种“自然实例”理论。该理论从应用程序的角度出发，试图对应用程序产生的实例的属性进行建模，然后为这些实例上的算法提供保证。该项目计划将机器学习纳入算法中，以解决整数规划。 PI提出了一个系统的发展的算法理论的切割平面，以确定家庭的实例，他们是证明有效的，并利用稀疏切割平面的计算优势。智力优势。这里提出的想法是新颖的，具有智力挑战性。自然系统的概念，就目前所知，以前没有研究过。虽然机器学习算法目前使用的是优化技术，但反过来还没有得到系统的研究。切割平面主要用于临时基础。没有系统的理论，切割平面算法是有效的问题。众所周知，稀疏性是切割平面算法的线性代数所必需的，但对于仅由稀疏不等式定义的多面体却知之甚少。这个EAGER项目的动机是一系列具有高度社会影响的优化问题，从运输和供应链物流，如运输，包裹递送，石化货物路由，车辆和移动的机器人路由到能源生产和分配。最终目标是研究算法优化方法，在未来十年内，这些方法可能导致能源生产和分配每年节省超过10亿美元，供应链中的燃料消耗减少50%，并消除极端天气干扰造成的能源短缺。这将通过创建优化算法来实现，这些算法的速度要快几个数量级，更强大，能够处理大量和混乱的数据。EAGER将为研究生和研究生提供研究培训，并在多个EAGER之间进行深入合作，并将通过在格鲁吉亚理工学院举办研讨会，在相关社区迅速传播研究成果。

Motivation.Discrete optimization problems have been studied by both the optimization and computer science communities. This EAGER project proposes to develop new approaches by synthesizing the ideas from the two communities by interdisciplinary collaboration between computer scientists and optimization specialists in mathematics and engineering. The goal is to develop rigorous and systematic approaches to discrete optimization problems by combining insights and state-of-the-art methods from integer programming (e.g., cutting planes and branch-and-bound) and algorithmic ideas from computer science (including online algorithms and machine learning). To be able to evaluate and compare methods on real-world instances, PIs plan to develop a theory of "natural instances". This theory starts from the application side, tries to model properties of the instances that arise from that application and then give guarantees for algorithms on such instances. The project plans to incorporate machine learning into algorithms to solve integer programs. PIs propose a systematic development of an algorithmic theory of cutting planes to identify families of instances for which they are provably efficient and to take advantage of the computational benefits of sparse cutting planes. Intellectual Merit. The ideas that are proposed here are novel and intellectually challenging. The notion of natural systems, insofar as known, has not been investigated previously. While machine learning algorithms currently use optimization technology, the reverse has not been systematically studied. Cutting planes are mainly used on an ad-hoc basis. There is no systematic theory regarding problems for which cutting plane algorithms are provably efficient. It is known that sparsity is needed in the linear algebra of cutting plane algorithms, but there is very little known about polyhedra that are defined by only sparse inequalities.Broader Impact. This EAGER project is motivated by a range of optimization problems of high societal impact from transportation and supply chain logistics such as palletizing, package delivery, petro-chemical cargo routing, vehicle and mobile robot routing to energy production and distribution. The ultimate goal is to study algorithmic optimization methods which over the next decade could lead to more than a billion dollars in annual savings in energy production and distribution, a 50% reduction in fuel consumption in supply chains and elimination of energy shortages caused by extreme weather disturbances. This will be possible by the creation of optimization algorithms that are orders of magnitude faster, more robust and capable of dealing with massive and messy data. This EAGER will provide research training for both graduate and postgraduate students and intensive collaboration among multiple EAGERs, and will provide rapid dissemination of the research throughout the relevant communities by hosting a workshop at Georgia Tech.