A Reformulation-Linearization Technique with Application to Production, Location, Distribution, and Design Problems

应用于生产、定位、分销和设计问题的重构线性化技术

• 批准号: 9121419
• 负责人: Hanif Sherali
• 金额: $ 15.85万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1996-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9121419&HistoricalAwards=false
• 关键词: Reformulation; Linearization; Technique; Application; Production

This project is concerned with the design of a new Reformulation-Linearization Technique (RLT) and the development of its application to various classes of problems arising in production, location-allocation, economics, and various engineering and systems design and operational contexts. At the heart of this methodology is a procedure developed under a previous National Science Foundation project for generating tight, higher dimensional, linear programming representations for linear and polynomial zero-one mixed-integer programming problems. The basic RLT procedure possesses a considerable degree flexibility that can be exploited to develop effective algorithmic variants. Various transformations and implementation schemes will be investigated in order to enhance the capability in solving both discrete and continuous nonconvex decision problems. The utility of the RLT scheme in generating facets and tight valid inequalities for important discrete classes of problems will also be explored. This will benefit other algorithms for mixed-integer zero-one problems. The methodology developed will be specialized to solve indefinite and concave quadratic programs, linear complementarily problems, location-allocation problems, and fixed-charge problems that arise in the different aforementioned applications.

该项目涉及一种新的重新配方线性化技术（RLT）的设计，并将其应用于生产、位置分配、经济、各种工程和系统设计和操作环境中出现的各种问题。该方法的核心是在之前的国家科学基金会项目下开发的一个程序，该项目用于生成线性和多项式零- 1混合整数规划问题的紧密、高维、线性规划表示。基本的RLT程序具有相当程度的灵活性，可用于开发有效的算法变体。为了提高求解离散和连续非凸决策问题的能力，将研究各种转换和实现方案。对于重要的离散类问题，RLT方案在生成切面和紧有效不等式方面的效用也将被探讨。这将有利于其他混合整数0 - 1问题的算法。所开发的方法将专门用于解决上述不同应用中出现的不定和凹二次规划、线性互补问题、位置分配问题和固定费用问题。