Collaborative Research: Reformulation-Linearization Technique for Discrete and Continuous Nonconvex Optimization with Applications

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

The research objective of this project is to develop theoretical and computational tools for solving difficult, large-scale, discrete and continuous nonconvex optimization problems. The work will focus on extending and refining a reformulation-linearization/convexification technique (RLT). The RLT is a methodological concept for enhancing problem solvability by constructing improved (tightened) mathematical models in lifted, higher-dimensional spaces. The intent of this study is to address several theoretical and algorithmic developments as well as computational implementation issues related to the RLT, and to identify and exploit mathematical structures that arise from applying it. Specifically, the work will include (1) an extension of the underlying RLT theory through the use of Lagrange interpolating polynomials to characterize structures of the convex hull of discrete sets by way of enhancing the ability to solve integer programs; (2) a unified RLT approach with semidefinite programming constructs along with filtering and basis-reduction techniques that can be used to design effective algorithms for solving discrete as well as continuous nonconvex optimization problems; and (3) the development of tailored methods for solving both discrete and nonlinear problems having certain special structures that arise in particular applications. The results of this study are expected to lead to more efficient tools for solving a variety of challenging nonconvex optimization programs, both discrete and continuous. The discrete programs arise in such diverse areas as clustering, cryptography, facility layout, logical inference, and scheduling, while the continuous nonconvex programs have applications in engineering design, network design, risk management, and Homeland Security. The research will also demonstrate how the algebraic properties of Lagrange interpolating polynomials can be exploited to analyze and generate cuts for mixed-integer and continuous nonlinear programming problems. Conceptually, the research will unify the realms of discrete and continuous optimization, and improve understanding of these domains.