Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Ottawa

$20,000.00

Applying Methods from Combinatorial Optimization in Solving Real World Problems

FY 2008-09

Summary
Many practically important problems are combinatorial in nature. Some examples of such problems include the design of reliable communication networks, fast printed circuit board production, scheduling problems and routing problems. Many such problems are known to belong to a class called "NP-hard", which is strong evidence that these problems are extremely difficult to solve, and that it is unlikely that efficient techniques for finding the optimal (i.e. the best) solution exist. The lack of efficient methods for such problems is of real importance as there exist large scale, real world instances requiring solutions. Fortunately, in practice, it is often satisfactory to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal solution. Our research objective is to enlarge the set of such problems which can be practically and satisfactorily solved. To achieve this objective we will use the following three approaches: 1) Investigate using closely-related relaxations of a problem to develop new, efficient methods which provide solutions which are guaranteed to lie within a satisfactory percentage of the optimal solution. 2) Exploit the underlying combintorial structure of a problem to provide the necessary tools for improved problem-specific implicit enumeration schemes for certain problems of interest. 3) Investigate constructing and applying combinatorial optimization models for applications arising in other areas of computer science.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
36740-2007
Name nom
Boyd, Sylvia
Department département
Information Technology and Engineering, 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
2008
Competition year année de concours
2007
Award amount
20000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
2
Nb partie
5
Application title
Applying Methods from Combinatorial Optimization in Solving Real World Problems
Keyword
NA
Application summary
Many practically important problems are combinatorial in nature. Some examples of such problems include the design of reliable communication networks, fast printed circuit board production, scheduling problems and routing problems. Many such problems are known to belong to a class called "NP-hard", which is strong evidence that these problems are extremely difficult to solve, and that it is unlikely that efficient techniques for finding the optimal (i.e. the best) solution exist. The lack of efficient methods for such problems is of real importance as there exist large scale, real world instances requiring solutions. Fortunately, in practice, it is often satisfactory to obtain solutions for these problems which, if not optimal, are at least guaranteed to lie within a certain satisfactory percentage of the optimal solution. Our research objective is to enlarge the set of such problems which can be practically and satisfactorily solved. To achieve this objective we will use the following three approaches: 1) Investigate using closely-related relaxations of a problem to develop new, efficient methods which provide solutions which are guaranteed to lie within a satisfactory percentage of the optimal solution. 2) Exploit the underlying combintorial structure of a problem to provide the necessary tools for improved problem-specific implicit enumeration schemes for certain problems of interest. 3) Investigate constructing and applying combinatorial optimization models for applications arising in other areas of computer science.