EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

An Improved Column Generation Algorithm Based on Minimum-Norm Multipliers

Dingfang Su, Jie Tao, Jiaxu Huang, Erzhan Gao

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →