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.
The objective of this project was to develop new mathematical tools that extend our nation’s scientific knowledge in solving certain classes of challenging discrete-choice and nonlinear optimization problems that are currently confronting society. The research was to both explore the underlying theory and to strategically apply this theory so as to solve larger and more complex problems than previously possible. General problem classes, as well as special instances having exploitable mathematical structures, were investigated for the purpose of developing powerful exact and heuristic solution procedures. In general, the types of problems considered are notoriously difficult to solve, and there is a strong need to design competitive solution algorithms because they arise in a variety of complex engineering contexts, including network design, product distribution, facility layout and location, game theory, production planning and control, and sequencing and scheduling, among others. This project has contributed toward key theoretical advances related to modeling and algorithmic design, which have facilitated the solution of difficult optimization problems, particularly as applied to several important contemporary problems including: risk management, homeland security, evacuation planning, resource allocation, sequencing and scheduling, educational planning, location and distribution, technology enhancement, network interdiction, and economic problems with economies of scale. For all these problems, enhanced modeling representations and improved algorithmic constructs have led to superior solution strategies. The main underlying tool that was developed and refined for achieving these advances is a novel Reformulation-Linearization Technique (RLT), which automatically restructures mathematical models in order to facilitate more effective algorithmic approaches. When augmented with special classes of valid inequalities (such as semidefinite cuts), this methodology affords a powerful device for solving the aforementioned types of challenging optimization problems. Some specific contributions in this regard that have the potential to significantly impact society are enumerated below. Development of an optimization framework for assisting governmental and regulatory agencies to make strategic decisions for selecting among alternatives and allocating scarce resources in order to manage risk in the event of hazardous occurrences such as nuclear disasters and gas-line ruptures. Design of a "nested event tree" modeling framework that can be used by homeland security in making critical allocation decisions of capability-related, intent-related, vulnerability-related, and consequence-related resources for combating terrorism. Formulation of strategies for evacuation planning that can assist local and State governmental agencies in optimally staging the evacuation of, and routing, residents in areas facing oncoming natural disasters such as floods or hurricanes. Construction of novel techniques, performed in collaboration with the U.S. Coast Guard, for allocating coastal sea-space sectors to vessels in order to conduct patrolling operations while balancing sector workloads and sector spans. Development of models and algorithms for solving maritime shipping-inventory problems and gas distribution-inventory problems in the natural gas industry, while specifically working with the Kuwait Petroleum Corporation (Kuwait) and the French company Air Liquide, which has operations in the U.S. Introduction of novel strategies for reducing the size of combinatorial optimization models, which are now being tested for the Department of Defense in connection with large-scale capacity planning problems that involve upgrading a fleet of diverse vehicles. Formulation of models and algorithms for recruiting teachers and assigning them to classes and time-slots within the Kuwait Public Educational System, and for determining equitable workload assignments for teaching assistants at Kuwait University. Derivation of novel models and decomposition-based algorithms, performed in concert with United Airlines, for solving operational scheduling problems in an integrated fashion while simultaneously considering fleet assignment, aircraft routing, and crew pairing decisions. A variety of contributions made in the context of modeling and analyzing cognitive radio networks, cooperative wireless networks, and sensor networks. This project has achieved advances in both basic and applied research, as well as human resource development. The research contributions have been disseminated through 50 archival journal publications, two books, and 40 presentations at various (inter)-national professional conferences and university seminars. Relative to education, several graduate students and additional collaborators at different universities have benefitted from joint work with the PIs. Four PhD students and four MS students have completed their graduate research on topics related to this project under the guidance of the PIs, and one additional PhD and two other MS students are in the process of completing their research studies. In addition, 40 other collaborators have worked with the PIs on related topics throughout the duration of the grant. Methodologies developed as part of this research effort are already becoming main-stream in graduate optimization courses, and are currently being taught in classes dealing with advanced discrete and nonlinear mathematical optimization problems.
