Grant: Alliance Grants
University of Toronto
$25,000.00
Principles of modeling and solving quadratic unconstrained binary optimization problems
EF 2023-24
Résumé
Quadratic Unconstrained Boolean Optimization (QUBO) is a mathematical modeling framework for challenging combinatorial optimization problems with applications in the design and operation of energy infrastructure (e.g., wind farm optimization), logistics (vehicle routing), manufacturing (scheduling), and a variety of other economically valuable problems. QUBO has received recent attention due to the nascent commercialization of hardware-based solvers using quantum and classical computation. Building on a three-year collaboration, this project seeks to develop a fundamental understanding of QUBO modeling: What characteristics of QUBO models lead to strong solver performance? What mathematical problem structures can be identified and exploited to produce smaller and more easily solved models? What are the basic building blocks of the science and mathematics of QUBO modeling?The project is structured with three research questions. First, we will develop the concept of a multi-level constraint (a mathematical constraint that evaluates to one of a finite set of values) that occurs commonly in binary linear programs and investigate how such constraints can be transformed to quadratic penalty functions in QUBO. Second, we will delve into the value of modeling with implied and redundant penalty functions with analogy to the important role of implied constraints in constrained optimization. Finally, we will examine the impact of sparsity on QUBO models, again motivated by the substantial role of sparsity in constrained optimization.The 18-month project will train two HQP on mathematical and empirical approaches to modeling and solving optimization problems, on using state-of-the-art hardware-based QUBO solvers, and on collaborating closely with industrial researchers at our industry collaborator, Fujitsu Consulting (Canada) Inc.
Programme
Alliance Grants
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
585990-2023
Name nom
Beck, Christopher JC
Department département
Mechanical and Industrial Engineering
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
25000
Program id
ALLRP
Program name en
Alliance Grants
Program name fr
Subventions Alliance
Group en
RESEARCH PARTNERSHIPS
Group fr
PARTENARIATS DE RECHERCHE
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2960
Research subject group en
Applied mathematics
Research subject group fr
Mathematical modelling
Research subject en
Mathématiques appliquées
Research subject fr
Modélisation mathématique
Application title
Principles of modeling and solving quadratic unconstrained binary optimization problems
Keyword
artificial intelligence; mathematical modelling; operations research; optimization; using custom hardware
Application summary
Quadratic Unconstrained Boolean Optimization (QUBO) is a mathematical modeling framework for challenging combinatorial optimization problems with applications in the design and operation of energy infrastructure (e.g., wind farm optimization), logistics (vehicle routing), manufacturing (scheduling), and a variety of other economically valuable problems. QUBO has received recent attention due to the nascent commercialization of hardware-based solvers using quantum and classical computation. Building on a three-year collaboration, this project seeks to develop a fundamental understanding of QUBO modeling: What characteristics of QUBO models lead to strong solver performance? What mathematical problem structures can be identified and exploited to produce smaller and more easily solved models? What are the basic building blocks of the science and mathematics of QUBO modeling?The project is structured with three research questions. First, we will develop the concept of a multi-level constraint (a mathematical constraint that evaluates to one of a finite set of values) that occurs commonly in binary linear programs and investigate how such constraints can be transformed to quadratic penalty functions in QUBO. Second, we will delve into the value of modeling with implied and redundant penalty functions with analogy to the important role of implied constraints in constrained optimization. Finally, we will examine the impact of sparsity on QUBO models, again motivated by the substantial role of sparsity in constrained optimization.The 18-month project will train two HQP on mathematical and empirical approaches to modeling and solving optimization problems, on using state-of-the-art hardware-based QUBO solvers, and on collaborating closely with industrial researchers at our industry collaborator, Fujitsu Consulting (Canada) Inc.