Distributed Projections for Mixed-Integer Programming
Abstract
Mixed-integer programming uses mathematical optimization algorithms to solve a wide range of high-impact decision-making problems spanning virtually all industries, including logistics, scheduling, revenue management, and machine learning. These problems can posesubstantial challenges to computers due to both scale and complexity. Numerous simplifications and approximations are typically deployed in mixed-integer programming models in order to facilitate practical solution times. As such, computational advances in optimization algorithms can enable better models and thus have widespread impact. In the past, algorithmic advances in mixed-integer programming have been matched by roughly equal speedups in hardware. The overall speedups were multiplicative, e.g. 4x algorithmic speedup and 3x hardware speedup leading to 12x overall. However, at present and for the foreseeable future, hardware advances are coming primarily from exploiting parallelism, i.e. simultaneous operations across multiple cores, processors, or computers. Unfortunately, mixed-integer programming algorithms cannot, in general, make good use of parallelism. A major bottleneck is the solution to linear programming problems, for which the dominant algorithms appear fundamentally serial in nature. Thus, hardware and algorithmic advances are decoupling, losing the multiplicative speedup factor. If left unaddressed, this issue will lead to substantial slowdowns in computational progress on mixed-integer programming problems.This proposal seeks to address this decoupling issue, focusing primarily on the use of parallel computing to solve linear programming programs (relaxations) arising from the solution of mixed-integer programming problems. The techniques considered are dimension-reduction in polyhedral projections, and the method of random projections. The general aim to decompose large-scale problems and distribute tasks evenly across processors. The project seeks both to lay the theoretical foundations for novel parallel approaches to linear programming, as well as to design and implement prototype algorithms. Extensive computational experiments will help guide the design and assess the robustness of such approaches.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 24, 2023
- Source ID
- N000142312632
Entities
People
- Chen Chen
Organizations
- Office of Naval Research
- Ohio State University
- United States Navy