A Potential Reduction Algorithm Allowing Column Generation

允许生成列的潜在减少算法

• 批准号: 8922636
• 负责人: Yinyu Ye
• 金额: $ 8.15万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-01 至 1993-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8922636&HistoricalAwards=false
• 关键词: Potential; Reduction; Algorithm; Allowing; Column

The goal of this research is to develop a potential reduction algorithm, based on recent results for analytic centers and their associated potential functions, that (1) allows column generation, (2) whose complexity does not depend on the full system of constraints and (3) that is implementable with practical efficiency. This type of a technique permits a great deal of flexibility for solving such optimization programs as semi-infinite programs, convex nonlinear programs and combinatorial optimization problems, in which the number of constraints is very large or some constraints are not explicitly known.

这项研究的目的是开发一种潜在的 简化算法，基于分析中心的最新结果 及其相关的势函数，即（1）允许列 （2）其复杂性不依赖于完整的 约束系统和（3）可实现的 实际效率。 这种技术允许很大的灵活性 为了求解这种半无限程序的优化程序， 凸非线性规划与组合优化 问题，其中约束的数量非常大，或者 某些约束不是明确已知的。