# All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers

arXiv: https://arxiv.org/abs/2410.15601 · HTML: https://mlsanity.com/paper/2410.15601/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Tune: A Research Platform for Distributed Model Selection and Training](https://mlsanity.com/paper/1807.05118/) (2018)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring](https://mlsanity.com/paper/2112.04906/) (2021)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Hybrid Pointer Networks for Traveling Salesman Problems Optimization](https://mlsanity.com/paper/2110.03104/) (2021)
- [Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks](https://mlsanity.com/paper/2307.04050/) (2023)
- [Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.16580/) (2024)
- [Solving a Class of Cut-Generating Linear Programs via Machine Learning](https://mlsanity.com/paper/2310.19920/) (2023)

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling](https://mlsanity.com/paper/2606.13133/) (2026)

## Abstract (arXiv)

We present a neural network-enhanced column generation (CG) approach for a parallel machine scheduling problem. The proposed approach utilizes an encoder-decoder attention model, namely the transformer and pointer architectures, to develop job sequences with negative reduced cost and thus generate columns to add to the master problem. By training the neural network offline and using it in inference mode to predict negative reduced costs columns, we achieve significant computational time savings compared to dynamic programming (DP). Since the exact DP procedure is used to verify that no further columns with negative reduced cost can be identified at termination, the optimality guarantee of the original CG procedure is preserved. For small to medium-sized instances, our approach achieves an average 45% reduction in computation time compared to solving the subproblems with DP. Furthermore, the model generalizes not only to unseen, larger problem instances from the same probability distribution but also to instances from different probability distributions than those presented at training time. For large-sized instances, the proposed approach achieves an 80% improvement in the objective value in under 500 seconds, demonstrating both its scalability and efficiency.