Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McMaster University

$33,000.00

Optimization algorithms: worst-case behaviours and related conjectures

EF 2010-11

Résumé
Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications in research and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. In many cases, these problems can be formulated or approximated as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. My research proposal focuses on the interconnections between these computationally successful algorithms for linear optimization, and the geometric and combinatorial structure of the input. The methodology is based on a combination of new polyhedral constructions with enhanced combinatorial and geometric properties and a tighter analysis of the currently established bounds. Supervision and training of highly qualified personnel is an essential part of my research proposal. As the head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students, and further strengthen the reputation of AdvOL as one of the leading research groups in Canada. This will develop optimization models, algorithms, software and produce Highly Qualified Personnel to assist Canadian enterprises in strategic sectors of the economy, such as information technology, design, manufacturing and transportation.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
311969-2010
Name nom
Deza, Antoine
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2010
Award amount
33000
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
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
1
Nb partie
5
Application title
Optimization algorithms: worst-case behaviours and related conjectures
Keyword
NSERC
Application summary
Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications in research and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. In many cases, these problems can be formulated or approximated as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. My research proposal focuses on the interconnections between these computationally successful algorithms for linear optimization, and the geometric and combinatorial structure of the input. The methodology is based on a combination of new polyhedral constructions with enhanced combinatorial and geometric properties and a tighter analysis of the currently established bounds. Supervision and training of highly qualified personnel is an essential part of my research proposal. As the head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students, and further strengthen the reputation of AdvOL as one of the leading research groups in Canada. This will develop optimization models, algorithms, software and produce Highly Qualified Personnel to assist Canadian enterprises in strategic sectors of the economy, such as information technology, design, manufacturing and transportation.