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

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

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.