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

本研究的重点是离散和连续非凸规划问题的新求解技术的制定和发展。该研究将围绕一种新的reformulation - linearizization - technique （RLT）展开，该技术已被开发用于生成紧密线性规划松弛，该松弛不仅可用于构建精确解算法，还可用于设计大型离散组合和连续非凸规划问题的启发式程序。对于线性混合整数0-1问题，提出了一种新的松弛层次结构，为构造从线性规划松弛到凸包表示的连续松弛谱提供了框架。层次结构提供了利用特殊结构的机会，例如广义/可变上界、覆盖、划分、打包约束和稀疏性。该方案的基本构造也可以扩展到设计连续的，非凸的，多项式规划问题的全局收敛过程。为了有效地处理通常由RLT过程生成的高维、大规模表示，建议研究各种约束和变量/列生成策略以及拉格朗日对偶方法。所开发的算法将在分配、设计、通信、生产和位置分配等一系列问题上进行测试。在求解整数规划问题时，紧线性规划松弛对于提高算法的有效性的重要性早已被认识到。本研究结果的潜在影响是提供一种工具（RLT），可以帮助统一概念，生成新的多面体结果，并设计有效的算法以及可证明的良好启发式，用于解决实践中经常出现的困难，离散和连续，非凸问题。这可能会导致通用的、实用的RLT实施策略的发展，并充分促进对其的理解，从而促进其融入公共领域软件。这种软件的普遍使用将显著提高该技术的使用效率。这将在许多应用程序中节省成本。

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.