Artificial Intelligence for Operation Research

About the Course

This course will introduce the use of artificial intelligence (AI) techniques in operation research (OR). AI is a rapidly growing field with applications in a wide range of areas, including OR. In this course, students will learn about the basic concepts of AI, as well as how AI can be used to solve OR problems.

The topics and the corresponding material are as follows:

1. Artificial Intelligence for Operation Research (AI4OR): Basics and Overview material slides
2. AI for Traveling Salesman Problem material slides
3. Sparse (Linear) Optimization material slides
4. Mixed-Integer Linear Programs material slides
5. Geometric Learning material slides
6. Semi-Definite Programming
7. Non-Convex Optimization
8. Graph Combinatorial Optimization and Intelligence
9. Combinatorial Optimization and Graph Neural Networks
10. Combinatorial Optimization and Game Theory

Prerequisites

Deep Learning, Operation Research

Artificial Intelligence for Operation Research (AI4OR): Basics and Overview

AI for Traveling Salesman Problem

Key papers

• Bresson, X., & Laurent, T. (2021). The transformer network for the traveling salesman problem. arXiv preprint arXiv:2103.03012.
• Kool, W., Van Hoof, H., & Welling, M. (2018). Attention, learn to solve routing problems!. arXiv preprint arXiv:1803.08475.
• Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., & Rousseau, L. M. (2018). Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018.
• Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.
• Bahdanau, D., Cho, K., & Bengio, Y. (2014). Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473.
• Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.
• Nazari, M., Oroojlooy, A., Snyder, L., & Takác, M. (2018). Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31.
• Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30.
• Joshi, C. K., Laurent, T., & Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.

Sparse Linear Optimization

Key papers

• Candes E, Tao T. Decoding by linear programming [J]. IEEE Transactions on Information Theory, 2005, 51: 4203-4215.
• D. L. Donoho, A. Maleki, and A. Montanari, "Message-passing algorithms for compressed sensing," Proceedings of the National Academy of Sciences, vol. 106, no. 45, pp. 18 914–18 919, 2009.
• Zhang Y. Theory of compressive sensing via l1-minimization: a non-RIP analysis and extensions [R]. Rice University, CAAM Technical Report TR08-11, 2008.
• Mousavi A, Patel A B, Baraniuk R G. A deep learning approach to structured signal recovery[C]//2015 53rd annual allerton conference on communication, control, and computing (Allerton). IEEE, 2015: 1336-1343.
• Kulkarni, K., Lohit, S., Turaga, P., Kerviche, R., & Ashok, A. (2016). Reconnet: Non-iterative reconstruction of images from compressively sensed measurements. In Proceedings of the IEEE conference on computer vision and pattern recognition (pp. 449-458).
• Shi W, Jiang F, Liu S, et al. Image compressed sensing using convolutional neural network[J]. IEEE Transactions on Image Processing, 2019, 29: 375-388.
• Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1), 1-122.
• Bach, F., Jenatton, R., & Mairal, J. (2011). Optimization with Sparsity-Inducing Penalties (Foundations and Trends(R) in Machine Learning).
• Xiang J, Dong Y, Yang Y. FISTA-net: Learning a fast iterative shrinkage thresholding network for inverse problems in imaging[J]. IEEE Transactions on Medical Imaging, 2021, 40(5): 1329-1339.
• Liu, J., & Chen, X. (2019, January). ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference on Learning Representations (ICLR).
• Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM journal on imaging sciences, 2009, 2(1): 183-202.
• Geng, C., Jiang, M., Fang, X., Li, Y., Jin, G., Chen, A., & Liu, F. (2023). HFIST-Net: High-throughput fast iterative shrinkage thresholding network for accelerating MR image reconstruction. Computer Methods and Programs in Biomedicine, 232, 107440.

Mixed-Integer Linear Programs

Key papers

• Berthold, T. (2006). Primal heuristics for mixed integer programs (Doctoral dissertation, Zuse Institute Berlin (ZIB)).
• Salimans, T., Ho, J., Chen, X., Sidor, S., & Sutskever, I. (2017). Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864.
• Huang, Z., Wang, K., Liu, F., Zhen, H. L., Zhang, W., Yuan, M., ... & Wang, J. (2022). Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123, 108353.
• Nair, V., Bartunov, S., Gimeno, F., Von Glehn, I., Lichocki, P., Lobov, I., ... & Zwols, Y. (2020). Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349.
• Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32.
• Paulus, M. B., Zarpellon, G., Krause, A., Charlin, L., & Maddison, C. (2022, June). Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning (pp. 17584-17600). PMLR.
• Gupta, P., Gasse, M., Khalil, E., Mudigonda, P., Lodi, A., & Bengio, Y. (2020). Hybrid models for learning to branch. Advances in neural information processing systems, 33, 18087-18097.
• Ding, J. Y., Zhang, C., Shen, L., Li, S., Wang, B., Xu, Y., & Song, L. (2020, April). Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference on artificial intelligence(Vol. 34, No. 02, pp. 1452-1459).
• Scavuzzo, L., Chen, F., Chételat, D., Gasse, M., Lodi, A., Yorke-Smith, N., & Aardal, K. (2022). Learning to branch with tree mdps. Advances in Neural Information Processing Systems, 35, 18514-18526.
• Duan, H., Vaezipoor, P., Paulus, M. B., Ruan, Y., & Maddison, C. (2022, June). Augment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning (pp. 5627-5642). PMLR.
• Sutton, R. S., McAllester, D., Singh, S., & Mansour, Y. (1999). Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12.

Geometric Learning

Key papers

• Boscaini, D., Masci, J., Rodolà, E., & Bronstein, M. (2016). Learning shape correspondence with anisotropic convolutional neural networks. Advances in neural information processing systems, 29.
• Tolstikhin, I., Bousquet, O., Gelly, S., & Schoelkopf, B. (2017). Wasserstein auto-encoders. arXiv preprint arXiv:1711.01558.
• Gong, F., Nie, Y., & Xu, H. (2022, October). Gromov-Wasserstein multi-modal alignment and clustering. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management (pp. 603-613).
• Mémoli, F. (2011). Gromov–Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics, 11, 417-487.
• Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., & Guibas, L. (2012). Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (ToG), 31(4), 1-11.
• Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006). Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences, 103(5), 1168-1172.
• Sun, J., Ovsjanikov, M., & Guibas, L. (2009, July). A concise and provably informative multi-scale signature based on heat diffusion. In Computer graphics forum (Vol. 28, No. 5, pp. 1383-1392). Oxford, UK: Blackwell Publishing Ltd.
• Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. science, 290(5500), 2319-2323.
• Qi, C. R., Su, H., Mo, K., & Guibas, L. J. (2017). Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition (pp. 652-660).
• Qi, C. R., Yi, L., Su, H., & Guibas, L. J. (2017). Pointnet++: Deep hierarchical feature learning on point sets in a metric space. Advances in neural information processing systems, 30.
• Sharma, G., Dash, B., RoyChowdhury, A., Gadelha, M., Loizou, M., Cao, L., ... & Kalogerakis, E. (2022, August). PriFit: learning to fit primitives improves few shot point cloud segmentation. In Computer Graphics Forum (Vol. 41, No. 5, pp. 39-50).
• Li, L., Sung, M., Dubrovina, A., Yi, L., & Guibas, L. J. (2019). Supervised fitting of geometric primitives to 3d point clouds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 2652-2660).
• Litany, O., Remez, T., Rodola, E., Bronstein, A., & Bronstein, M. (2017). Deep functional maps: Structured prediction for dense shape correspondence. In Proceedings of the IEEE international conference on computer vision (pp. 5659-5667).
• Halimi, O., Litany, O., Rodola, E., Bronstein, A. M., & Kimmel, R. (2019). Unsupervised learning of dense shape correspondence. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 4370-4379).

Semi-Definite Programming

Key papers

• coming soon

Non-Convex Optimization

Key papers

• coming soon

Graph Combinatorial Optimization and Intelligence

Key papers

• coming soon

Combinatorial Optimization and Graph Neural Networks

Key papers

• coming soon

Combinatorial Optimization and Game Theory

Key papers

• coming soon

Contact

If you have any comments, questions or suggestions about the material, please contact huangxikun@amss.ac.cn