Deep Chebyshev Center-Based Column Generation

Maria Baier () and Dirk Lebiedz ()
Additional contact information
Maria Baier: Ulm University
Dirk Lebiedz: Ulm University

Chapter Chapter 74 in Operations Research Proceedings 2023, 2025, pp 581-587 from Springer

Abstract: Abstract Chebyshev center-based column generation, CCG, is a gently stabilized variant of classical column generation, CG, that relies on dual information provided by central interior points to identify new improving columns [3]. From a dual perspective, the basic algorithm corresponds to the well-known Chebyshev center cutting plane method, which draws on weak dual bounds and converges still rather slow in practice [1, 3]. We present deep Chebyshev center-based column generation, DCCG, a sophistication operating on stronger bounds and employing deeper cuts. Besides giving first numerical evidence of its superiority over both classical and state-of-the-art Chebyshev center-based column generation, we provide interesting analytical insights that lay the foundation for further improvements in the realm of column generation and beyond.

Keywords: Column generation; Chebyshev centers; (Mixed-)Integer programming; Large-scale optimization; Cutting plane methods (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-58405-3_74

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_74

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().