Eager: Discrete Optimization Algorithms for 21st Century Algorithms

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

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.