Novel Polyhedral Approaches to Integer and Quadratically Constrained Quadratic Programming
Abstract
Mathematical optimization problems are found in numerous areas of science, engineering, and decision-making. Examples include network design, scheduling, resource allocation, production, supply chain management, and power systems. Their ubiquity underscores the importance of developing fast solution algorithms. However, tackling these problems directly is very challenging. Instead, most approaches rely on solving related, simpler problems, that are called relaxations. Solving a relaxation gives a way to obtain an estimate of the solution to the original hard problem. Techniques to construct, improve, and extract solutions from relaxations are fundamental steps towards the solution of complex problems. The goal of the proposed effort is to devise, implement, and test new technologies for a variety of optimization problems. The research will focus on the fundamental classes of (Mixed)-Integer (IP) and Quadratically Constrained Quadratic (QCQP) problems. Current techniques only allow to obtain accurate relaxations for such problems if a large computational burden is incurred for their construction, and an even larger burden for their solution. This is due to the fact that these techniques are, very often, applied as a black-box, i.e., they are agnostic to the specificity of the problem at hand. Moreover, the fast computation of near-optimal solutions is a challenge. The effort will bypass these concerns by devising problem-dependent techniques, building on, and extending tools from duality theory, geometry, graph theory, and order theory. Strong emphasis will be placed in the practical computation of good-quality solutions to large and challenging problem cases.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 14, 2024
- Source ID
- FA95502310697
Entities
People
- Yuri Faenza
Organizations
- Air Force Office of Scientific Research
- Trustees of Columbia University in the City of New York
- United States Air Force