A New Approach to Ralaxation in Integer Programming

整数规划松弛的新方法

• 批准号: 8508142
• 负责人: Monique Guignard-Spielberg
• 金额: --
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1985
• 资助国家: 美国
• 起止时间: 1985-09-15 至 1989-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8508142&HistoricalAwards=false
• 关键词: New; Approach; Ralaxation; Integer; Programming

The focus of this project is on the analysis of a new relaxation approximation for integer programming problems and on the design of algorithms exploiting this technique. This new relaxation, called composite decomposition, can be viewed as a generalization of both surrogate and Lagrangean relaxations. The principal investigator has recently proved that it dominates Lagrangean, surrogate and LP relaxations, in the sense that the bounds on the optimum are at least as good and probably better. The aim of this proposal is to study dual ascent heuristic methods which appear best suited to the composite decomposition relaxation. Emphasis will be placed on classes of problems which lend themselves naturally to this kind of decomposition, such as network location problems, generalized assignment/allocation problems, and multiple choice problems, as well as specially structured problems with a few general side constraints.

该项目的重点是分析新的放松措施 整数规划问题的近似和设计 利用这种技术的算法。 这种新的放松，称为 复合分解，可以看作是两者的推广 代理松弛和拉格朗日松弛。 主要研究者 最近证明，它优于拉格朗日，代理和LP 放松，在这个意义上，最佳的界限至少是 一样好，也许更好 这项研究的目的是研究双 上升启发式方法，似乎最适合的复合 分解松弛 重点将放在类 这些问题很自然地被分解了， 例如网络定位问题、广义指派/分配 问题，多项选择题，以及特殊结构的 有几个一般性的边约束的问题。