A Unifying Approach for Discrete and Continuous Nonconvex Optimization with Applications to Operational and Design Problems

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

This research project is concerned with a unifying solution approach, namely the Reformulation-Linearization/Convexification Technique (RLT), that has been developed for generating tight relaxations for large classes of discrete combinatorial and continuous nonconvex programming problems. The various contributions addressed in this project involve the development of both general theoretical and algorithmic concepts, as well as specialized procedures for several important applications, along with the investigation of related implementation issues accompanied by extensive computational tests. For linear mixed-integer 0-1 problems we explore the design of effective RLT relaxations, enhanced by conditional logic implications, and embedded within a dynamic Lagrangian relaxation constraint generation scheme. In the context of continuous nonconvex problems, we propose the study of various strategies for generating tight manageable relaxations for devising computationally effective global optimization RLT approaches to solve a wide class of factorable nonlinear programs. In order to effectively cope with the size and structure of the relaxations that are typically generated by RLT, various Lagrangian dual/relaxation, aggregation, penalty function, trust region, and conjugate/deflected subgradient methods are suggested for investigation. These ideas are proposed to be further explored in the context of a variety of specific applications including radar pulsing and bit-mapping problems, machine scheduling problems, two-stage stochastic mixed-integer problems involving integer recourse decisions, ship design problems, and various operational and strategic planning air traffic management problems faced at airports as well as in the enroute airspace. Discrete and continuous nonconvex programming problems arise in a host of practical operational, strategic planning, and system or engineering design applications. Several recent advances have been made in the development of algorithms for solving such classes of problems. At the heart of these approaches is a sequence of linear (or convex) programming relaxations that drive the solution process, and the success of such algorithms is strongly dependent on the strength or tightness of these relaxations. This research project is concerned with a unifying solution approach, namely the Reformulation-Linearization/Convexification Technique (RLT), that has been developed for generating tight relaxations for not only constructing exact solution algorithms, but also to design powerful heuristic procedures for large classes of discrete combinatorial and continuous nonconvex programming problems. The various contributions addressed in this project involve the development of both general theoretical and algorithmic concepts, as well as specialized procedures for several important applications. The impact of this study will be the development of a comprehensive technology that unifies many important concepts and offers insights into problem structures and modeling strategies, as well as provides a construct for generating tight relaxations.