Grant: Discovery Grants Program - Individual
Carleton University
$28,000.00
Large Scale Optimization: Algorithms and Applications
EF 2016-17
Résumé
Optimization is the science of finding the best possible solution to practical problems, e.g. the best allocation of limited resources, or the shortest route between two places. Advanced optimization techniques are vital when the problems are large and complex. For example, how should an airline assign aircraft and crews to routes and schedules to minimize total costs given requirements for aircraft maintenance, constraints on crew flight times, location of equipment and crews, and passenger travel demands? Large problems require efficient computer algorithms for solution.
From the earliest days, optimization techniques have advanced in tandem with innovations in computing, however developments in computing have progressed rather rapidly in recent years. Parallel computing platforms are now readily available in both multi-core desktop machines and commercial computing clouds. Massive amounts of data are available online, and our interconnected world allows optimization decisions to be applied rapidly. Better optimization techniques are needed to handle the larger and more complex problems that arise in this environment, techniques that can take advantage of the advances in computing technology. At the same time, our greater interconnectedness allows the rapid application of optimized decisions.
The main goal of the proposed research is to develop faster optimization techniques that can solve the much larger problems we are now facing . There are three main thrusts.
First, better optimization solution techniques are needed to handle the much larger problems that businesses, organizations and governments now face. Real innovation is needed here: existing methods do not scale at the rate dictated by the explosion of data made available by the internet. As far as possible, any new techniques should take advantage of the now readily available parallel computing platforms. I plan to explore innovative parallel algorithms based on techniques developed in my earlier research. These will be implemented in software and tested on large problems to demonstrate their improvements over existing techniques and software.
Second, as optimization models become much larger and more complex, consisting of many thousands of relationships, errors are easier to introduce and harder to find and remove. One serious class of error results in a model that has no solution. I am proposing new techniques for analyzing this kind of error in an important class of models with the goal of identifying the smallest possible subset of the model that contains the error. This helps the modeller to identify and correct the problem. The new techniques will be implemented in software and tested.
Finally, I will look at some specific applications enabled by these new techniques. Examples: compressed sensing for transmitting signals as efficiently as possible, and automatic classification of data at the least expected cost (e.g. classifying patients as having cancer or not, given costs for medical tests and estimated costs of misclassification).
Most large Canadian organizations, businesses, and government entities (including the military) make use of large-scale optimization because being efficient by making the best use of limited resources is vital to their success, hence they will directly benefit from the proposed research. This applies whether they develop and use optimization models in-house, or whether they buy optimization services or packages from vendors. Ordinary Canadians will benefit from cheaper products and more effective services when these large scale optimization techniques are applied by the businesses they patronize and the organizations and government entities they interact with.
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
RGPIN-2014-04056
Name nom
Chinneck, John
Department département
Systems and Computer Engineering
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
28000
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
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
Partie
3
Nb partie
5
Application title
Large Scale Optimization: Algorithms and Applications
Keyword
NSERC
Application summary
Optimization is the science of finding the best possible solution to practical problems, e.g. the best allocation of limited resources, or the shortest route between two places. Advanced optimization techniques are vital when the problems are large and complex. For example, how should an airline assign aircraft and crews to routes and schedules to minimize total costs given requirements for aircraft maintenance, constraints on crew flight times, location of equipment and crews, and passenger travel demands? Large problems require efficient computer algorithms for solution.
From the earliest days, optimization techniques have advanced in tandem with innovations in computing, however developments in computing have progressed rather rapidly in recent years. Parallel computing platforms are now readily available in both multi-core desktop machines and commercial computing clouds. Massive amounts of data are available online, and our interconnected world allows optimization decisions to be applied rapidly. Better optimization techniques are needed to handle the larger and more complex problems that arise in this environment, techniques that can take advantage of the advances in computing technology. At the same time, our greater interconnectedness allows the rapid application of optimized decisions.
The main goal of the proposed research is to develop faster optimization techniques that can solve the much larger problems we are now facing . There are three main thrusts.
First, better optimization solution techniques are needed to handle the much larger problems that businesses, organizations and governments now face. Real innovation is needed here: existing methods do not scale at the rate dictated by the explosion of data made available by the internet. As far as possible, any new techniques should take advantage of the now readily available parallel computing platforms. I plan to explore innovative parallel algorithms based on techniques developed in my earlier research. These will be implemented in software and tested on large problems to demonstrate their improvements over existing techniques and software.
Second, as optimization models become much larger and more complex, consisting of many thousands of relationships, errors are easier to introduce and harder to find and remove. One serious class of error results in a model that has no solution. I am proposing new techniques for analyzing this kind of error in an important class of models with the goal of identifying the smallest possible subset of the model that contains the error. This helps the modeller to identify and correct the problem. The new techniques will be implemented in software and tested.
Finally, I will look at some specific applications enabled by these new techniques. Examples: compressed sensing for transmitting signals as efficiently as possible, and automatic classification of data at the least expected cost (e.g. classifying patients as having cancer or not, given costs for medical tests and estimated costs of misclassification).
Most large Canadian organizations, businesses, and government entities (including the military) make use of large-scale optimization because being efficient by making the best use of limited resources is vital to their success, hence they will directly benefit from the proposed research. This applies whether they develop and use optimization models in-house, or whether they buy optimization services or packages from vendors. Ordinary Canadians will benefit from cheaper products and more effective services when these large scale optimization techniques are applied by the businesses they patronize and the organizations and government entities they interact with.