Accelerating Column Generation in Highly Degenerate Integer Programming Problems with Template Pricing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914470678233088 |
|---|---|
| author | Marshall, Luke Shah, Prachi Dey, Santanu S. |
| author_facet | Marshall, Luke Shah, Prachi Dey, Santanu S. |
| contents | We propose a new pricing strategy for column generation (CG), referred to as Template pricing. This method is motivated by the desire to coordinate solutions of different pricing subproblems in order to accelerate the convergence of the CG process and simultaneously obtain good quality integer feasible solutions. Instead of finding a column with the optimal reduced cost, Template pricing tries to maximize the similarity of columns with a given template vector, while restricting the search to columns with suitable reduced cost. We present an exact and heuristic method (based on Lagrangian relaxation) to efficiently solve the Template pricing problem. We conduct extensive computational experiments on benchmark instances of the Generalized Assignment Problem (GAP). Our results demonstrate that Template pricing can significantly accelerate the CG algorithm, especially in the presence of significant degeneracy, where several benchmark GAP instances solved over 1000x faster than Dantzig pricing, and over 100x with adaptive dual-smoothing. Template pricing allows us to achieve CG optimal bounds on all 1735 ISA instances, finding stronger bounds in 43% and improved integer solutions in 9% of these instances than previously released. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_12070 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Accelerating Column Generation in Highly Degenerate Integer Programming Problems with Template Pricing Marshall, Luke Shah, Prachi Dey, Santanu S. Optimization and Control 90C05 We propose a new pricing strategy for column generation (CG), referred to as Template pricing. This method is motivated by the desire to coordinate solutions of different pricing subproblems in order to accelerate the convergence of the CG process and simultaneously obtain good quality integer feasible solutions. Instead of finding a column with the optimal reduced cost, Template pricing tries to maximize the similarity of columns with a given template vector, while restricting the search to columns with suitable reduced cost. We present an exact and heuristic method (based on Lagrangian relaxation) to efficiently solve the Template pricing problem. We conduct extensive computational experiments on benchmark instances of the Generalized Assignment Problem (GAP). Our results demonstrate that Template pricing can significantly accelerate the CG algorithm, especially in the presence of significant degeneracy, where several benchmark GAP instances solved over 1000x faster than Dantzig pricing, and over 100x with adaptive dual-smoothing. Template pricing allows us to achieve CG optimal bounds on all 1735 ISA instances, finding stronger bounds in 43% and improved integer solutions in 9% of these instances than previously released. |
| title | Accelerating Column Generation in Highly Degenerate Integer Programming Problems with Template Pricing |
| topic | Optimization and Control 90C05 |
| url | https://arxiv.org/abs/2604.12070 |