Eager: Discrete Optimization Algorithms for 21st Century Algorithms

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

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.