Grant: Discovery Grants Program - Individual
University of Ottawa
$25,000.00
Applying Methods from Combinatorial Optimization in Solving Large-Scale Real World Problems
FY 2015-16
Summary
Many practically important optimization problems are combinatorial in nature. Some examples include the minimum cost design of reliable communication networks, fast printed circuit board production, the building of genetic evolutionary trees as well as the optimization of various scheduling and routing problems. Unfortunately, may such problems belong to a class called ""NP-hard"", which is considered strong evidence that they are extremely difficult to solve, and that it is highly unlikely that we will find techniques for solving them that are guarantee to be practical and efficient in all cases. The lack of efficient methods for such problems is of significant importance as there exist large-scale, real world instances requiring solutions. Fortunately, in practice, it is often sufficient to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal (best) solution, which in many cases is much more viable task.
Our research objective is to enlarge the set of such NP-hard problems arising from applied combinatorial optimization models which can be practically and satisfactorily solved. To achieve this goal we will use the following three approaches:
1) Investigate developing new and improved efficient methods for such problems which provide
solutions guaranteed to lie within a satisfactory percentage of the optimal solution.
2) Investigate ways to improve the success rate of current methods which attempt to find an exact
optimal solution for such problems.
3) Investigate ways of applying combinatorial optimization models and methods to applications
arising in other areas of Computer Science.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
36740-2013
Name nom
Boyd, Sylvia
Department département
Electrical Engineering and Computer Science , School of
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2013
Award amount
25000
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
3
Nb partie
5
Application title
Applying Methods from Combinatorial Optimization in Solving Large-Scale Real World Problems
Keyword
NSERC
Application summary
Many practically important optimization problems are combinatorial in nature. Some examples include the minimum cost design of reliable communication networks, fast printed circuit board production, the building of genetic evolutionary trees as well as the optimization of various scheduling and routing problems. Unfortunately, may such problems belong to a class called ""NP-hard"", which is considered strong evidence that they are extremely difficult to solve, and that it is highly unlikely that we will find techniques for solving them that are guarantee to be practical and efficient in all cases. The lack of efficient methods for such problems is of significant importance as there exist large-scale, real world instances requiring solutions. Fortunately, in practice, it is often sufficient to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal (best) solution, which in many cases is much more viable task.
Our research objective is to enlarge the set of such NP-hard problems arising from applied combinatorial optimization models which can be practically and satisfactorily solved. To achieve this goal we will use the following three approaches:
1) Investigate developing new and improved efficient methods for such problems which provide
solutions guaranteed to lie within a satisfactory percentage of the optimal solution.
2) Investigate ways to improve the success rate of current methods which attempt to find an exact
optimal solution for such problems.
3) Investigate ways of applying combinatorial optimization models and methods to applications
arising in other areas of Computer Science.