[![INFORMS Journal on Computing Logo](https://INFORMSJoC.github.io/logos/INFORMS_Journal_on_Computing_Header.jpg)](https://pubsonline.informs.org/journal/ijoc)

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

This archive is distributed in association with the [INFORMS Journal on
Computing](https://pubsonline.informs.org/journal/ijoc) under the [MIT License](LICENSE).

The software and data in this repository are a snapshot of the software and data
that were used in the research reported on in the paper 
[An Improving Column is All You Need: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://doi.org/10.1287/ijoc.2024.1005) by Amira Hijazi, Osman Ozaltin and Reha Uzsoy.


## Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2024.1005

https://doi.org/10.1287/ijoc.2024.1005.cd

Below is the BibTex for citing this snapshot of the repository.

```
@misc{ahijazi2026,
  author =        {Amira Hijazi and Osman Ozaltin and Reha Uzsoy},
  publisher =     {INFORMS Journal on Computing},
  title =         {{An Improving Column is All You Need: Enhancing Column Generation for Parallel Machine Scheduling via Transformers}},
  year =          {2026},
  doi =           {10.1287/ijoc.2024.1005.cd},
  url =           {https://github.com/INFORMSJoC/2024.1005},
  note =          {Available for download at https://github.com/INFORMSJoC/2024.1005},
}  
```

## Description

This repository provides code and data for reproducing the computational experiments in the paper "An Improving Column is All You Need: Enhancing Column Generation for Parallel Machine Scheduling via Transformers". 
The paper presents a neural network-enhanced column generation approach (CG NN-DP) for a parallel machine scheduling problem. The approach uses an encoderdecoder attention mechanism, specifically a transformer model with a pointer layer, to identify columns, i.e., job processing sequences, with negative reduced costs to be added to the restricted master problem (RMP). Exact solution of a pricing subproblem using Dynamic Programming (DP) verifies that no further columns with negative reduced costs can be identified at termination, preserving the optimality guarantee.
By training the pointer transformer model offline and using it in inference mode during column generation, CG NN-DP achieves significantly faster convergence than the traditional column generation (CG) procedure, which relies solely on solving the pricing subproblem via DP. Computational experiments demonstrate that CG NN-DP generalizes effectively beyond the maximum number of jobs used during training and performs well on out-of-distribution instances. The paper also compares CG NN-DP with a CG procedure using an efficient pricing heuristic (CG Heuristic-DP). For mediumsized instances, both methods yield improvements of 65% to 90% over traditional CG, while CG NN-DP outperforms CG Heuristic-DP as the number of jobs increases. For large-scale and out-of-distribution instances, CG NN-DP converges more quickly and achieves lower relative RMP objective values, demonstrating both scalability and efficiency.


## Repository Structure
- **Training_Data/**:  pkl data files for training the neural network.
- **src/**: Python source code for all column generation and model training experiments.
- **Checkpoints/**: Trained pointer‑transformer model checkpoint (`final_PointerTransformerMachine.pkl`).
- **Results/**: Pre-generated figures from the paper are available in the results directory.

## Training_Data
The Training_Data/ directory contains .pkl files storing training data for the pointer transformer model. Each file consists of multiple training instances, where each instance corresponds to a single column‑generation iteration of a single‑machine pricing subproblem.
Each training instance includes:

the feature vector of the machine (0, 0, dual value),
job‑level feature vectors (processing time, weight, dual), and
the associated target job sequence (y) generated by the exact dynamic programming (DP) pricing algorithm.

File names encode the problem size.
For example, instances12M40NSchedules.pkl contains training instances generated from a problem with 12 machines and 40 jobs. Each pickled instance within the file corresponds to one single‑machine pricing subproblem solved during a column‑generation iteration.

## src
Python source code for all experiments

| File | Description |
|------|-------------|
| `CG_Main.py` | Main file for running column generation experiments with DP pricing, NN-DP pricing, and Heuristic-DP|
| `CGModulesDefinitions.py` | Core column generation components: input data generation (uniform and weibull), initial columns generation, master problem, DP pricing, Heuristic pricing and the IP formulation of the original problem |
| `PointerTransformerModelDefinition.py` | transformer pointer model architecture and feature preparation for single‑machine pricing subproblems used during CG inference|
| `Functions.py` | Shared utilities and helper functions |
|`PointerTransformerTraining.py` | Training script for the transformer pointer model|

# Building and Running
## install dependence:

## Training the Neural Network
To train the pointer‑transformer pricing model, run:
```bash
python3 PointerTransformerTraining.py
```
Training uses data from the Training_Data/ directory, where each training instance corresponds to a single column‑generation iteration of a single‑machine pricing subproblem.
The training process was executed using two Nvidia A100 GPUs.

## Running Column Generation Experiments
To run the column generation experiments, run on linux:
```bash
python3 CG_Main.py --M 20 --N 500 --init_cols 100 --timelimit 900
```

This command:
- Runs **10 different problem instances** of the parallel machine scheduling problem with **20 machines (M)** and **500 jobs (N)**.
- Initializes the restricted master problem with **100 columns per machine** (`init_cols = 100`).
- Evaluates both pricing approaches:
  - **Heuristic-DP**
  - **NN‑DP** using the checkpoint of the trained model
- Enforces a **time limit of 900 seconds** (`timelimit`) for each run of each method.
- Produces performance comparison figures as in the Results/20M_500N.png

Testing experiments were conducted on a 64-bit Linux server equipped
with dual Intel Xeon Gold 6226 CPUs, using a total of 24 cores running at 2.7 GHz, and 187 GB of memory.
For each instance size, the set of 10 instances was executed with 10 CPU cores and 128 GB of memory.

## Support
For questions or issues regarding the software, please open an issue on this GitHub repository.
