Grant: Discovery Launch Supplement
Université de Montréal
$12,500.00
Theory and Algorithms for Mixed-Integer Nonlinear Programming
EF 2024-25
Résumé
Mixed-Integer Non-Linear Programming (MINLP) is a powerful tool to model decision-making problems in complex systems. It has shown great potential in numerous applications including network design, logistics, portfolio optimization, healthcare, and machine learning. MINLP is one of the most challenging classes of optimization problems that combines the difficulties of discrete variables and nonlinear objectives and/or constraints. Remarkable progress in theory, algorithms, and hardware has empowered solvers to be increasingly efficient at solving large-scale Mixed-Integer Linear Programming (MILP) problems. Despite such advances in MILP, even the state-of-the-art solvers still struggle with many MINLP problems. To enable further advancement in MINLP, it is crucial to examine the properties of specific nonlinear structures.
In this proposed research program, we aim to (1) broaden the scope of theoretical development in MINLP. We will uncover, characterize, and exploit discrete analogues of convexity displayed in broad classes of nonlinear functions over discrete domains. This class of discrete nonlinear structures is ubiquitous in MINLP far beyond convex optimization with integer variables---nonconvex functions restricted to discrete domains can possess such structures. We will (2) devise scalable and versatile exact solution methods for MINLP. MINLP with high nonlinearity typically does not admit compact formulations that are directly solvable by the state-of-the-art optimization tools. Specialized algorithms tend not to work with complicated sets of constraints that arise in real-world applications. We propose to devise efficient and versatile algorithms that allow general constraints and obtain exact discrete optimal solutions within a reasonable time. We aim to (3) apply our theoretical and algorithmic results to address real-world challenges. We will tackle practical decision-making problems, including fair and robust resource allocation in bike sharing and sensor energy management.
In summary, this research program will broaden our understanding of general MINLP. We will combine our theoretical contributions with the established MILP results to devise exact solution methods and solve classes of currently intractable MINLP problems. We will tackle practical problems under the theme of fairness in resource allocation. Furthermore, this program will provide training opportunities for HQP in theory, algorithms, and applications of MINLP.
Programme
Discovery Launch Supplement
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
DGECR-2024-00331
Name nom
Yu, Qimeng
Department département
Informatique et recherche opérationnelle
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
12500
Program id
DGECR
Program name en
Discovery Launch Supplement
Program name fr
Supplément Tremplin vers la découverte
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Theory and Algorithms for Mixed-Integer Nonlinear Programming
Keywords
mixed-integer programming; nonlinear optimization; submodularity; discrete convexity; exact methods; cutting planes; delayed constraint generation; polyhedral; convex hull
Application summary
Mixed-Integer Non-Linear Programming (MINLP) is a powerful tool to model decision-making problems in complex systems. It has shown great potential in numerous applications including network design, logistics, portfolio optimization, healthcare, and machine learning. MINLP is one of the most challenging classes of optimization problems that combines the difficulties of discrete variables and nonlinear objectives and/or constraints. Remarkable progress in theory, algorithms, and hardware has empowered solvers to be increasingly efficient at solving large-scale Mixed-Integer Linear Programming (MILP) problems. Despite such advances in MILP, even the state-of-the-art solvers still struggle with many MINLP problems. To enable further advancement in MINLP, it is crucial to examine the properties of specific nonlinear structures.
In this proposed research program, we aim to (1) broaden the scope of theoretical development in MINLP. We will uncover, characterize, and exploit discrete analogues of convexity displayed in broad classes of nonlinear functions over discrete domains. This class of discrete nonlinear structures is ubiquitous in MINLP far beyond convex optimization with integer variables---nonconvex functions restricted to discrete domains can possess such structures. We will (2) devise scalable and versatile exact solution methods for MINLP. MINLP with high nonlinearity typically does not admit compact formulations that are directly solvable by the state-of-the-art optimization tools. Specialized algorithms tend not to work with complicated sets of constraints that arise in real-world applications. We propose to devise efficient and versatile algorithms that allow general constraints and obtain exact discrete optimal solutions within a reasonable time. We aim to (3) apply our theoretical and algorithmic results to address real-world challenges. We will tackle practical decision-making problems, including fair and robust resource allocation in bike sharing and sensor energy management.
In summary, this research program will broaden our understanding of general MINLP. We will combine our theoretical contributions with the established MILP results to devise exact solution methods and solve classes of currently intractable MINLP problems. We will tackle practical problems under the theme of fairness in resource allocation. Furthermore, this program will provide training opportunities for HQP in theory, algorithms, and applications of MINLP.