Dyadic Programming(White paper tracking 21-000000686)
Abstract
Approved for Public ReleaseA rational number is dyadic if its denominator is a power of two. Dyadic numbers are important for numeri,cal computations because they have a finite binary representation, which makes them well suited for arithmetic operations on compute,rs. Most linear programming solvers use fixed-precision floating points, thus approximating rational numbers by dyadic numbers of fi,xed size, and this sometimes leads to numerical issues. The proposed project will investigate dyadic solutions to linear programs, w,here no a priori bound is imposed on the size of the binary representation. This research area was initiated recently by Ahmad Abdi,, Gerard Cornuejols, Bertrand Guenin and Levent Tuncel.Improvements in integer programming software over the last twenty five years h,ave revolutionized our ability to solve practical problems arising in engineering, transportation, telecommunications, and many othe,r areas, be they civilian or military. The use of general-purpose cuts was a key ingredient of this transformation. This includes th,e discovery of lift-and-project cuts and the subsequent revival of the Gomory cuts by Egon Balas and Gerard Cornuejols under prior O,NR support. The new project "dyadic programming" will establish the foundations for a class of optimization problems that sits somew,here between linear programming and integer programming.Tools from integer programming, such as the Hermite normal form, are central, to this research. Interestingly, dyadic programs can be solved more efficiently than integer programs. In fact, dyadic programs can, be solved in polynomial time. The topics covered in this research will range from the foundations of this area, to algorithms, char,acterizations of primal and dual dyadic solutions, and sparsity of optimal solutions.The proposed project is expected to improve our, ability to solve certain classes of optimization problems that lie between linear programming and integer programming. The broad im,pact of the tools developed in this project will contribute to strengthen US technological leadership. The training of researchers a,t the forefront of software creation is another major goal of this project.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 13, 2022
- Source ID
- N000142212528
Entities
People
- Gérard Cornuéjols
Organizations
- Carnegie Mellon University
- Office of Naval Research
- United States Navy