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
中文摘要
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
-
批准号:0969169
-
项目类别:Standard Grant
-
资助金额:$15.0万
-
财政年份:2010
-
负责人:Hanif Sherali
-
依托单位:
Integrated Operations Planning Models and Algorithms for the Airline Industry
-
批准号:0754236
-
项目类别:Standard Grant
-
资助金额:$33.91万
-
财政年份:2008
-
负责人:Hanif Sherali
-
依托单位:
Enhancing the Solvability of Discrete and Continuous Nonconvex Programs with Applications to Production, Design, and Operational Problems
-
批准号:0552676
-
项目类别:Standard Grant
-
资助金额:$32.06万
-
财政年份:2006
-
负责人:Hanif Sherali
-
依托单位:
International Conference on Complementarity, Duality, and Global Optimization; August 15-17, 2005; Virginia Tech - Blacksburg, VA
-
批准号:0455807
-
项目类别:Standard Grant
-
资助金额:$3.0万
-
财政年份:2005
-
负责人:Hanif Sherali
-
依托单位:
GOALI: Demand Driven Fleet Management Analysis, Models, and Algorithms for the Airline Industry
-
批准号:0245643
-
项目类别:Standard Grant
-
资助金额:$34.78万
-
财政年份:2003
-
负责人:Hanif Sherali
-
依托单位:
A Unifying Approach for Discrete and Continuous Nonconvex Optimization with Applications to Operational and Design Problems
-
批准号:0094462
-
项目类别:Continuing Grant
-
资助金额:$46.13万
-
财政年份:2001
-
负责人:Hanif Sherali
-
依托单位:
Exploratory Research on Engineering the Transport Industries (ETI): Air-Traffic Management and Control Issues in the Terminal Area and in the Enroute National Airspace
-
批准号:0085640
-
项目类别:Standard Grant
-
资助金额:$11.5万
-
财政年份:2000
-
负责人:Hanif Sherali
-
依托单位:
Discrete and Continuous Nonconvex Optimization with Applications to Production, Distribution, and Design Problems
-
批准号:9812047
-
项目类别:Standard Grant
-
资助金额:$21.56万
-
财政年份:1998
-
负责人:Hanif Sherali
-
依托单位:
A Reformulation-Linearization Technique with Application to Production, Location, Distribution, and Design Problems
-
批准号:9121419
-
项目类别:Continuing Grant
-
资助金额:$15.85万
-
财政年份:1992
-
负责人:Hanif Sherali
-
依托单位:
A New Reformulation Technique for Tightening Relaxations of Some Combinatorial Optimization Problems with Application tothe General Linear Complementarity Problem
-
批准号:8807090
-
项目类别:Continuing Grant
-
资助金额:$11.5万
-
财政年份:1989
-
负责人:Hanif Sherali
-
依托单位:
Research Initiation: the Mixed-Integer Bilinear ProgrammingProblem With Extensions to Zero-One Quadratic Programs
-
批准号:8103732
-
项目类别:Continuing Grant
-
资助金额:$4.8万
-
财政年份:1981
-
负责人:Hanif Sherali
-
依托单位:
海外基金