Grant: Discovery Grants Program - Individual
University of British Columbia
$41,000.00
New Synergies Between Combinatorial and Continuous Optimization
FY 2020-21
Summary
Optimization refers to any problem where we have a list of feasible solutions and a measure on their relative desirability. The goal is to find the feasible solution which is most desirable. Intuitively, we partition these into one of two types: minimum cost problems or maximum
profit. One does not need examples to understand that optimizing is a universal phenomenon which arises in essentially every organization. It is used to run hospitals, airlines, power grids and also to inform public policy.
The dual faces of optimization are modelling and algorithms. Optimization remains vibrant partly by its continual infusion into new models and requirements arising in state-of-the-art applications in engineering, physics, medicine, statistics and computer science. These models place challenging new requirements on solution techniques or algorithms. In the countless ads for employees with expertise in analytics, data science, AI, logistics and machine learning, I often observe that organizations are seeking personnel with a maturity in optimization. It takes time to learn how to recognize opportunities for optimization in the wild. It also takes maturity to argue against the use of optimization when it does not make sense! The consummate optimizer has the confidence gained from understanding theoretical trade-offs (runtime efficiency, degree of optimality, code simplicity) together with intuition acquired from numerical experience.
This proposal's focus is on new synergies between combinatorial and continuous optimization. There has been an increasing tendency for
conceptual developments in the continuous and discrete realms to occur together for mutual benefit. Examples include advances in semi-definite programming, polynomial optimization, electrical flows in networks and submodular optimization. This interplay is a long-term positive force for optimization and this proposal identifies several themes which have the potential for expanding the interface between continuous and discrete optimization.
Given the current demand for big-data models, it is natural that our research themes often have relatively simple algorithms (such as greedy or local search) at their core. For instance, one theme proposes a parameter for a polytope which measures precisely the performance of the (or a) greedy algorithm on the polytope. This notion of "greedy gap" is inspired by matroids but also has interesting connections to norm-constrained optimization. In a second theme, our objective is to extend the breakthrough results for the continuous greedy algorithm to be applicable to (max sum) diversity maximization problems. Diversity maximization is often used in the ubiquitous problem of clustering data points. This is done by choosing a small set of items which are "far apart" so that they act as cluster representatives.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-06141
Name nom
Shepherd, Bruce
Department département
Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2020
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
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
Computer communications
Area of application fr
Téléinformatique
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Installment
inst:1-5
Partie
5
Nb partie
5
Application title
New Synergies Between Combinatorial and Continuous Optimization
Keyword
NSERC
Application summary
Optimization refers to any problem where we have a list of feasible solutions and a measure on their relative desirability. The goal is to find the feasible solution which is most desirable. Intuitively, we partition these into one of two types: minimum cost problems or maximum
profit. One does not need examples to understand that optimizing is a universal phenomenon which arises in essentially every organization. It is used to run hospitals, airlines, power grids and also to inform public policy.
The dual faces of optimization are modelling and algorithms. Optimization remains vibrant partly by its continual infusion into new models and requirements arising in state-of-the-art applications in engineering, physics, medicine, statistics and computer science. These models place challenging new requirements on solution techniques or algorithms. In the countless ads for employees with expertise in analytics, data science, AI, logistics and machine learning, I often observe that organizations are seeking personnel with a maturity in optimization. It takes time to learn how to recognize opportunities for optimization in the wild. It also takes maturity to argue against the use of optimization when it does not make sense! The consummate optimizer has the confidence gained from understanding theoretical trade-offs (runtime efficiency, degree of optimality, code simplicity) together with intuition acquired from numerical experience.
This proposal's focus is on new synergies between combinatorial and continuous optimization. There has been an increasing tendency for
conceptual developments in the continuous and discrete realms to occur together for mutual benefit. Examples include advances in semi-definite programming, polynomial optimization, electrical flows in networks and submodular optimization. This interplay is a long-term positive force for optimization and this proposal identifies several themes which have the potential for expanding the interface between continuous and discrete optimization.
Given the current demand for big-data models, it is natural that our research themes often have relatively simple algorithms (such as greedy or local search) at their core. For instance, one theme proposes a parameter for a polytope which measures precisely the performance of the (or a) greedy algorithm on the polytope. This notion of "greedy gap" is inspired by matroids but also has interesting connections to norm-constrained optimization. In a second theme, our objective is to extend the breakthrough results for the continuous greedy algorithm to be applicable to (max sum) diversity maximization problems. Diversity maximization is often used in the ubiquitous problem of clustering data points. This is done by choosing a small set of items which are "far apart" so that they act as cluster representatives.