Tight Polyhedral Relaxations for Discrete and Continuous Nonconvex Problems with Applications to Production, Distribution, and Design Problems

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

9521398 Sherali This research is focused on the formulation and development of new solution techniques for discrete and continuous nonconvex programming problems. The research will revolve around a new Reformulation-Linearization-Technique (RLT) that has been developed for generating tight linear programming relaxations that can be used not only to construct exact solution algorithms, but also to design heuristic procedures for large classes of discrete combinatorial and continuos nonconvex programming problems. For linear mixed-integer 0-1 problems, a new hierarchy of relaxations is presented that provides a framework for constructing a spectrum of continuous relaxations spanning from the linear programming relaxation to the convex hull representation. The hierarchy provides opportunity to exploit special structures such as generalized/variable upper bounds, covering, partitioning, packing constraints, and sparsity. The basic constructs of the scheme can also be extended to devise globally convergent procedures for continuous, nonconvex, polynomial programming problems. To effectively cope with the higher dimensional, large-scale representations that are typically generated by the RLT procedure, various constraint and variable/column generation strategies and Lagrangian dual approaches are suggested for investigation. The developed algorithm will be tested on a host of problems drawn from distribution, design, telecommunication, production, and location-allocation problems. The importance of having tight linear programming relaxations to enhance the effectiveness of algorithms for solving integer programming problems has long been recognized. The potential impact of the outcome of this research is to provide a tool (the RLT) that can help unify concepts, generate new polyhedral results, and design effective algorithms along with provable good heuristics for hard, discrete and continuous, nonconvex problems that arise often in practice. This may lead to the development of general, pract ical, RLT implementation strategies and promote its understanding sufficiently so as to facilitate its assimilation into public domain software. Common usage of such software will significantly improve the efficiency of usage of the technique. This will produce savings in cost in a host of applications.