Project Description

Automatic algorithm discovery involves the automatic generation and optimization of algorithms that solve specific problems. Various techniques have been used for this purpose. Genetic algorithms evolve a population of potential algorithms through selection, mutation, and crossover, effectively exploring a vast solution space to discover optimal algorithms for specific tasks. Mixed-Integer Nonlinear Programming (MINLP) formulates the algorithm discovery problem as an optimization model, where constraints ensure the convergence of the algorithm and the objective encodes the algorithm's merit function. Machine learning, particularly reinforcement learning, trains models to perform tasks, where the model iteratively improves its algorithms based on performance feedback. Recently, large language models (LLMs) have been combined with genetic programming for algorithm discovery. Among these existing techniques, MINLP-based approaches offer two major advantages: Due to the use of global optimization algorithms, they provide certified global optimality with respect to desirable objectives such as minimum total computational cost or per-iteration complexity. Moreover, MINLP-based approaches offer the flexibility to explicitly enforce constraints essential for the algorithm's validity and efficiency, such as convergence, stability, and error bounds. These constraints cannot be strictly enforced in approaches such as genetic programming and reinforcement learning. However, the downside of global optimization algorithms is their scalability. Furthermore, existing MINLP approaches fail to consider multiple instances and lack worst-case guarantees over the functional space. The goal of this proposal is to develop scalable MINLP-based approaches for algorithm discovery.  

Start Date

After Feb 2025 

Postdoc Qualificatios

PhD in industrial engineering, operations research, chemical engineering, electrical engineering, applied math, computer science, or related fields.
Research expertise in one or more of the followings areas: linear/nonlinear/mixed-integer programming/machine learning/optimization under uncertainty.
Fluent programming in one of the following programming languages: Python/Julia/C++. 

Co-advisors

Name: Can Li
email: canli@purdue.edu
Affiliation: Davidson School of Chemical Engineering
website: https://canli1.github.io/

Name: Mohit Tawarmalani
email: mtawarma@purdue.edu
Affiliation: Mitchell E. Daniels, Jr. School of Business
Website: https://web.ics.purdue.edu/~mtawarma/

Name: David Bernal
email: dbernaln@purdue.edu
Affiliation: Davidson School of Chemical Engineering
website: https://secquoia.github.io/1-bernalde 

Bibliography

[1] Lucas Parada, Mauricio Sepúlveda, Carlos Herrera, and Victor Parada. Automatic generation of algorithms for the binary knapsack problem. In 2013 IEEE Congress on Evolutionary Computation, pages 3148–3152. IEEE, 2013.
[2] Alexander Mitsos, Jaromił Najman, and Ioannis G. Kevrekidis. Optimal deterministic algorithm generation. Journal of Global Optimization, 71:891–913, 8 2018. ISSN 0925-5001.
doi: 10.1007/s10898-018-0611-8.
[3] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes,
Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser,
Grzegorz Swirszcz, David Silver, Demis Hassabis, and Pushmeet Kohli. Discovering faster
matrix multiplication algorithms with reinforcement learning. Nature, 610:47–53, 10 2022.
ISSN 0028-0836. doi: 10.1038/s41586-022-05172-4.
[4] Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024.