Study of Lagrangean Decompositions

拉格朗日分解的研究

• 批准号: 9014901
• 负责人: Monique Guignard-Spielberg
• 金额: --
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-06-15 至 1995-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9014901&HistoricalAwards=false
• 关键词: Study; Lagrangean; Decompositions

Lagrangean decomposition (LD) and Lagrangean decomposition/aggregation (LD/A) are powerful tools for computing bounds in integer programming. This is a project to study LD for minmax problems and for separable problems with a nonlinear objective function. The research will develop solutions for LD/A problems which decompose into relatively easy subproblems, some or all of them with the integrality property, so that the LD/A bound is as good as (i.e. equal to) the corresponding Lagrangean Relaxation bound. Moreover the LD/A procedure occasionally yields the optimal solution in the not infrequent instance when the subproblems have identical solutions. There is a need for investigation into the LD and LD/A minimax problems. There is a strong potential for a breakthrough in computational efficiency.

拉格朗日分解（LD）和拉格朗日 分解/聚合（LD/A）是计算的强大工具 integer programming的定义 这是一个研究LD的项目， minmax问题和可分问题的非线性 目标函数 该研究将为LD/A开发解决方案 问题分解成相对容易的子问题，一些或 它们都具有完整性，因此LD/A界 与相应的拉格朗日方程一样好（即等于） 松弛束缚。 此外，LD/A程序偶尔会产生 最佳解决方案在不罕见的情况下，当 子问题有相同的解。 有必要对LD和LD/A极大极小进行研究 问题 有很大的潜力取得突破， 计算效率