Nonlinear Approaches to Discrete and Combinatorial Optimization
Abstract
Discrete and combinatorial optimization problems frequently arise in both civil and military applications dealing with resource allocation, decision making, and artificial intelligence. Many such problems can be formulated as (non-convex) binary integer programs, or optimization problems where variables can take only 0 or 1 values. The non-convex 0-1 nature of these problems can make them extremely hard to solve. Some of the most powerful general-purpose approaches for solving such problems are based on hierarchies of successive "relaxed" reformulations that are convex (and thus easy to solve) and converge to an exact solution of the original problem in a finite number of steps. However, each next step requires solving reformulations of increased size, limiting the practical applicability of this methodology to a few initial levels of the hierarchies. The proposed project aims at developing a completely new type of hierarchy based on a fundamentally different approach. Motivated by encouraging preliminary results, the effort will investigate several research directions aiming to establish the proposed novel hierarchy to a broad class of decision and optimization problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 29, 2024
- Source ID
- FA95502310300
Entities
People
- Sergiy Butenko
Organizations
- Air Force Office of Scientific Research
- Texas Engineering Experiment Station
- United States Air Force