Discrete and Continuous Nonconvex Optimization with Applications to Production, Distribution, and Design Problems

点击翻译按钮获取中文摘要

9812047Sherali This grant provides funding for the development and study of a new methodology, the Reformulation-Linearization/Convexification Technique (RLT), for generating tight relaxations that can be used to construct exact solution methods as well as to design powerful heuristic procedures for large classes of discrete combinatorial and continuous nonconvex programming problems. For linear mixed-integer 0-1 problems, specialized RLT relaxations that are enhanced by conditional logic implications will be developed and embedded within a dynamic Lagrangian Relaxation constraint generation scheme. In the context of continuous nonconvex programs, new theoretically convergent and computationally effective global optimization RLT approaches will be developed to solve a wide class of factorable nonlinear programs. Extensions and specializations for minimax problems that arise in situations dealing with multiple criteria and equity issues, and for general integer/discrete problems will also be explored. In order to effectively cope with the size and structure of the relaxations that are typically generated by RLT, various Lagrangian dual, aggregation, penalty function, trust region, and conjugate/deflected subgradient methods will be investigated. These ideas and methods will be applied to design novel approaches to solve a variety of location-allocation problems, telecommunication and pipe-network design problems, machine scheduling problems, and air traffic control management problems. If successful, the results of this research will lead to the development of a new comprehensive technology that unifies many important concepts and offers insights into problem structures and modeling strategies. Operations Research analysts and practitioners will be able to use this methodology to construct tight model representations, generate strong valid inequalities, and design effective procedures for solving hard, discrete and continuous, nonconvex problems that arise often in practice. The research canl contribute toward the design of various computational tools that may be incorporated in public domain software for solving such classes of problems.