Combinatorial Optimization: Algorithms and Applications
Abstract
Integer programming software has undergone major transformations in recent decades, revolutionizing our ability to solve practical p""roblems arising in engineering, transportation, telecommunications, and many other areas, be they civilian or military. Some of thes""e improvements are due to faster computers, but the bulk comes from better integer programming algorithms. The use of general-purpos"e cuts was a key ingredient of this transformation. This includes the discovery of lift-and-project cuts and the subsequent revival of the Gomory cuts.Both project were performed by two of the principal investigators under prior ONR support.The purpose of this" project is to continue this revolution. In the current data-rich environment, it is essential to understand the interplay between d""ata and optimization algorithms. Traditionally, coefficients arising from a random process (such as expected cost) are obtained sepa""rately from the optimization step, their estimation being used in the optimization problem to obtain solutions. An interesting quest"ion is whether the estimation and optimization tasks can be performed separately without compromising the quality of the end solutio"n. Adifferent direction of research tries to capitalize on two very different ways of representing polyhedra, through a system of i""nequalities on the one hand, or as the sum of a polytope expressed as the convex hull of extreme points and a polyhedral cone expres"sed as a nonnegative combination of extreme rays. The interplay between these two representations can be critical when dealing with large-scale integer programming problems. A third direction of this proposal is to extend integer programming solvers with optimization techniques based ondecision diagrams. The main motivation is that decision diagrams provide complementary strengths to existin"g integer programming technology. By utilizing relaxed and restricted decision diagrams of limited size, we can increase the strengt""h of the diagram until a desired maximum amount of time or memory is reached. In particular, relaxed decision diagrams explicitly al""low to trade off memory versus computation time, which is a desirably feature since computer memory has become abundant these days.""The proposed project is expected to further improve integer programming solvers, and to better integrate massive data into the opti"mization process. Progress in our ability to solve large-scale integer programs will improve efficiency in an extremely broad range" of activities including production, logistics, capital investment, health care, cryptanalysis, finance, radio frequency management" and many others. The broad impact of the tools developed in this project will contribute to strengthen US technological leadership.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 26, 2018
- Source ID
- N000141812129
Entities
People
- Egon Balas
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy