Overview
Many machine-learning systems can learn patterns from images or sensor data, but they often struggle when decisions must follow strict rules. Real-world tasks may involve budgets, capacities, safety limits, or actions that are required or forbidden.
Led by Georg Martius, this project investigated how neural networks can be combined with combinatorial optimization—mathematical methods for choosing the best option from many discrete possibilities. The project developed ways to embed optimization algorithms into learning systems, allowing AI to learn from data while making decisions that respect predefined constraints. It ran from 2021 to 2024.
Key results
- Developed methods for integrating integer-programming and other combinatorial optimization problems into neural networks.
- Created neuro-algorithmic policies that combine learned representations with structured algorithms, improving generalization to new combinatorial problems.
- Developed methods for planning directly from visual input, connecting perception from images with decision-making in environments involving difficult search problems.
- Introduced techniques for training neural networks through discrete optimization procedures, even when these procedures are not naturally differentiable.
- Developed LPGD, a general framework for backpropagation through embedded optimization layers, making it easier to train systems that contain classical solvers.
- Demonstrated how optimization components can serve as trainable building blocks rather than being treated as separate tools.
Why it matters
The project provides a foundation for AI systems that connect perception with structured, constraint-aware decision-making. Such systems could help robots plan actions safely, enable logistics systems to allocate limited resources, and support applications in scheduling, planning, and operations management.
The approach does not replace classical optimization solvers. Instead, it integrates them into larger learning pipelines so that neural networks can interpret data while established algorithms handle rules and constraints. This combination could make AI systems more reliable and adaptable, although their performance still depends on how accurately the relevant constraints and optimization problem are modelled.
This project produced the following peer-reviewed publications:
- Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius. “CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints”. In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139. Proceedings of Machine Learning Research. PMLR, July 2021, pp. 8443–8453. url: https://proceedings.mlr.press/v139/paulus21a.html.
- Marin Vlastelica, Michal Rolinek, and Georg Martius. “Neuro-algorithmic Policies Enable Fast Combinatorial Generalization”. In: Proceedings of the 2021 International Conference on Machine Learning (ICML). July 2021. url: https://proceedings.mlr.press/v139/vlastelica21a.html.
- Marco Bagatella, Mirek Olšák, Michal Rolínek, and Georg Martius. “Planning from Pixels in Environments with Combinatorially Hard Search Spaces”. In: Advances in Information Processing Systems (NeurIPS 2021). 2021. url: https://openreview.net/forum?id=XgGUUaKgips.
- Subham Sahoo, Anselm Paulus, Marin Vlastelica, Vít Musil, Volodymyr Kuleshov, and Georg Martius. “Backpropagation through Combinatorial Algorithms: Identity with Projection Works”. In: Proceedings of the Eleventh International Conference on Learning Representations. May 2023. url: https://openreview.net/forum?id=JZMR727O29.
- A. Paulus, G. Martius, and V. Musil. “LPGD: A General Framework for Backpropagation through Embedded Optimization Layers”. In: Proceedings of the 41st International Conference on Machine Learning (ICML). Vol. 235. Proceedings of Machine Learning Research. PMLR, July 2024, pp. 39989–40014. url: https://proceedings.mlr.press/v235/paulus24a.html.
