Generalized column generation for linear programming

• 成果类型: Article
• 署名作者: Oguz, O
• 署名单位: Ihsan Dogramaci Bilkent University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.48.3.444.7729
• 发表日期: 2002
• 页码: 444-452
• 关键词: column generation; simplex algorithm; linear programming

摘要

Column generation is a well-known and widely practiced technique for solving linear programs with too many variables or constraints to include in the initial formulation explicitly. Instead, the required column information is generated at each iteration of the simplex algorithm. This paper shows that, even if the number of variables is low enough for explicit inclusion in the model with the available technology, it may still be more efficient to resort to column generation for some class of problems.