Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization

This is the code for our TMLR-Paper: Mielke et al., "Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization", Transactions on Machine Learning Research, 2026

Method Overview

Our method leverages graph neural networks (GNNs) to augment existing heuristics for combinatorial optimization (CO) problems. We train a GNN to predict parameters that influence the behavior of these heuristics, leading to improved solution quality.

Specifically, for edge-selection problems (where the solution is a subset of edges in a graph), the GNN predicts edge-level scores, based on which we scale the edge weights of the input graph. The modified graph is then fed into the heuristic. By employing fast heuristics, we can integrate them directly into the training loop, which allows us to use the same pipeline for both training and inference. Once trained, the GNN-augmented heuristic serves as a direct replacement for the original heuristic, maintaining efficiency and usability while enhancing solution quality.

Preference-Based Gradient Estimation (PBGE)

The GNN plus heuristic pipeline is trained self-supervised, indirectly optimizing the CO problem's objective. The central challenge in this setup is in backpropagating through the (non-differentiable) heuristic. To address this, we introduce Preference-Based Gradient Estimation (PBGE), which estimates gradients by comparing pairs of solutions sampled from the given heuristic. The CO problem's objective function allows us to determine which of the two solutions performs better, and this preference signal is used to train the model, thus eliminating the need for ground-truth solutions.

Usage

Use python -m data_generation.generate_dataset to generate a dataset. Make sure to configure the dataset parameters in that file.

For training, configure the model and hyperparameters in training-config.yml, then run python -m training.train.

Citation

If you use our work, please cite the paper as follows:

@article{pbge,
    title = {Preference-Based Gradient Estimation for {ML}-Guided Approximate Combinatorial Optimization},
    author = {Mielke, Arman and Bauknecht, Uwe and Strauss, Thilo and Niepert, Mathias},
    journal = {Transactions on Machine Learning Research},
    year = {2026},
    url = {https://openreview.net/forum?id=2S224XC378}
}