An Improved Column Generation Algorithm Based on Minimum-Norm Multipliers
Mathematics · 10.03.2026 · 14 (6) · 931
DOI: 10.3390/math14060931 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 10.03.2026. Verfasst von Dingfang Su und 3 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Humanities and Social Sciences of the Ministry of Education, Shanghai Office of Philosophy and Social Science.
Abstract (Originalsprache)
Column generation is a fundamental technique for solving large-scale combinatorial optimization problems such as unit commitment and vehicle routing, yet its performance is often limited by dual oscillation. This study explores the intrinsic cause of this phenomenon from the perspective of shadow price theory and demonstrates that dual oscillation arises from the lack of marginal interpretability of Lagrange multipliers when multiple dual solutions coexist. To address this issue, an improved column generation framework is proposed in which traditional multipliers are replaced with minimum-norm multipliers that possess clear economic meaning and act as directional shadow prices. A generalized pricing subproblem is formulated, and partial minimum-norm multipliers are obtained through convex quadratic optimization to guide column generation. Numerical experiments on a simplified single-period unit commitment case and large-scale cutting stock problems showed that the proposed approach eliminated invalid column generation and achieved speedy convergence to the optimal solution within only two iterations for the unit commitment case, and the classical column generation exhibited slow convergence with dual oscillation in large-scale scenarios while the improved algorithm achieved fast and stable convergence. The results indicate that the stabilization method enhances the consistency of dual variables and provides a more robust foundation for the theoretical and practical development of column generation algorithms.
Förderung
- Humanities and Social Sciences of the Ministry of Education
- Shanghai Office of Philosophy and Social Science
Zitieren
APA
Su, D., Tao, J., Huang, J., & Gao, E. (2026). An Improved Column Generation Algorithm Based on Minimum-Norm Multipliers. Mathematics, 14(6), 931. https://doi.org/10.3390/math14060931
Vancouver
Su D, Tao J, Huang J, Gao E. An Improved Column Generation Algorithm Based on Minimum-Norm Multipliers. Mathematics. 2026;14(6):931. doi:10.3390/math14060931
BibTeX
@article{Su2026,
author = {Su, Dingfang and Tao, Jie and Huang, Jiaxu and Gao, Erzhan},
title = {An Improved Column Generation Algorithm Based on Minimum-Norm Multipliers},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {6},
pages = {931},
doi = {10.3390/math14060931}
}
EUVIMED