Enhancing the Solvability of Discrete and Continuous Nonconvex Programs with Applications to Production, Design, and Operational Problems

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

This project deals with theoretical and algorithmic developments, as well as computational implementation issues related to the Reformulation-Linearization/Convexification Technique (RLT). In the context of 0-1 and general discrete mixed-integer programs, a dynamic Lagrangian relaxation strategy will be developed to automatically generate judicious RLT-enhanced reformulations. Specializations for minimax problems will also be investigated. Extensions to general integer or discrete programs, including the development of a new class of Chvatal-Gomory Tier Cuts, as well as extensions to convex-constrained problems will be studied. In the arena of continuous nonconvex factorable programming problems, various RLT constraint generation and filtering strategies for constructing tight manageable relaxations will be developed, including a new class of semidefinite cuts for enhancing the model representation. Applications arising in national airspace planning and air-traffic management, production scheduling, engineering design under uncertainty, and wireless communication network design will be explored. The study of these applications will encompass polyhedral analyses of certain combinatorial optimization problems such as the generalized vertex packing problem and the asymmetric traveling salesman problem.The results of this study will advance concepts and offer insights into problem structures and modeling strategies, as well as provide a construct for generating tight relaxations leading to effective procedures for solving the above types of problems. The contributions will advance optimization theory as well as impact the aforementioned application domains. In particular, the air-traffic management application proposed for study will be investigated in cooperation with the Federal Aviation Administration (FAA), and will benefit society by reducing delays and related airline costs, as well as by enhancing the safety and operational efficiency of the national airspace. Students from across the College of Engineering will be involved in this research effort, and the technology generated by this project will be disseminated via public domain software.