Decision Diagrams for Combinatorial Optimization: Algorithms and Applications
Abstract
Improvements in integer programming and combinatorial optimization software over the last thirty years have revolutionized our ability to solve practical problems arising in engineering, transportation, telecommunications, and many other areas, be they civilian or military. Some of these improvements are due to faster computers, but the bulk comes from algorithmic improvements, including the development of general-purpose methods. The purpose of this project is to continue this revolution, in particular the development of decision diagram methodology to further expand the availability and scalability of combi-natorial optimization in applications. The utilization of decision diagrams for optimization was rst developed some ten years ago by the PI and collaborators, and this area of research has since attracted a broader interest. Decision diagrams provide complementary strengths to existing technology such as integer programming. By utilizing relaxed and restricted decision diagrams of limited size, we can increase the strength of the diagram until a desiredmaximum amount of time or memory is reached. In particular, relaxed decision diagrams explicitly allow to trade o memory versus computation time, which is a desirably feature since computer memory has become abundant these days.Under the current ONR support, the PI and collaborators have already made substantial progress in the application of decision diagram technology to integer programming solvers. In particular, the PI has developed cut generation and dual bound computations using decision diagrams, which have been successfully embedded in integer linear and nonlinear programming solvers. One of the papers that was developed with ONR support received the 2020 INFORMS Computing Society Harvey J. Greenberg Research Award. This proposal aims to further advance the development of decision diagram technology for combinatorial optimization, with the ultimate purpose of scalable and robust algorithms for realistic large-scale applications. Methodologically, four main topics of investigation are proposed: 1) the compilation of decision diagrams by means of iterative constraint separation, 2) the extension of decision diagrams to represent multiple solutions simultaneously, 3) the development of new primal heuristics, and 4) an investigation of variable ordering strategies on the size and performance of decision diagrams. We develop these methodologies on three fundamental combinatorial optimization problems: graph coloring, bin packing, and capacitated vehicle routing. This sequence of applications allows to systematically extend and generalize thedeveloped methodology for increasingly complex domains. The proposed project is expected to improve our ability to solve complex and/or large-scale combinatorial optimization problems, which can potentially improve eciency in an extremely broad range of activities including production, logistics, capital investment, health care, cryptanalysis, nance, radio frequency management and many others. The broad impact of the tools developed in this project will contribute to strengthen US technological leadership. The training of researchers at the forefront of software creation is another major goal of this project.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 06, 2021
- Source ID
- N000142112240
Entities
People
- Willem Van Hoeve
Organizations
- Carnegie Mellon University
- Office of Naval Research
- United States Navy