课题基金 / 基金详情

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

Tight Polyhedral Relaxations for Discrete and Continuous Nonconvex Problems with Applications to Production, Distribution, and Design Problems
离散和连续非凸问题的紧多面体松弛及其在生产、分配和设计问题中的应用
批准号:
9521398
负责人:
Hanif Sherali
金额:
$21.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1995
资助国家:
美国
项目状态:
已结题
起止时间:
1995-12-01 至 1999-05-31

项目摘要

项目成果

Hanif Sherali的其他基金

相似基金

相关文献

中文摘要
翻译
9521398 Sherali本研究致力于提出和发展离散和连续非凸规划问题的新的求解技术。这项研究将围绕着一种新的重构线性化技术(RLT)展开,该技术已被开发用于产生紧线性规划松弛,该松弛不仅可以用于构造精确解算法,而且可以用于设计大类离散组合和连续非凸规划问题的启发式过程。对于线性混合整数0-1问题,提出了一种新的松弛族,它为构造从线性规划松弛到凸壳表示的连续松弛谱提供了一个框架。该层次结构提供了利用特殊结构的机会,例如广义/可变上界、覆盖、划分、包装约束和稀疏性。该方案的基本结构还可以扩展到设计连续、非凸、多项式规划问题的全局收敛过程。为了有效地处理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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: Reformulation-Linearization Technique for Discrete and Continuous Nonconvex Optimization with Applications
Integrated Operations Planning Models and Algorithms for the Airline Industry
Enhancing the Solvability of Discrete and Continuous Nonconvex Programs with Applications to Production, Design, and Operational Problems
International Conference on Complementarity, Duality, and Global Optimization; August 15-17, 2005; Virginia Tech - Blacksburg, VA
海外基金