Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Carleton University

$20,000.00

Solution methods and bounding techniques for hard combinatorial optimization problems

EF 2006-07

Résumé
When solving large-scale discrete optimization problems (that is, problems in which the decision variables represent indivisible quantities), one often finds good solutions using heuristics or approximation algorithms.  One way to measure the quality of a computed solution is by comparing its cost with a lower bound (in the case of minimization) obtained by solving a relaxation of the problem.  Having such a lower bound can be invaluable as it gives information on how far away from optimality the computed solution is.  The quality of such a bound is often critical to the performance of enumerative methods such as branch and bound. The proposed research has two related directions.  The first direction is to develop theoretical and empirical techniques for analyzing the quality of a relaxation of a discrete optimization problem.  Over the years, theoretical guarantees on how good certain relaxations approximate particular problems have been obtained.  Yet many of the analyses are problem-specific and are not readily transferrable to other problems.  The development of a general technique will permit a more systematic analysis of relaxations.  The second direction is to obtain a better understanding of what are commonly known as lift-and-project methods.  These methods can be used to obtain arbitrarily strong relaxations but the difficulty is that if used directly, they incur much computation overhead in practice.  The proposed research will study how to exploit problem structure and symmetry so that these methods can be applied in practice to problems that are known to be computationally challenging.  Problems studied will include the travelling tournament problem which has immediate applications in sports scheduling and an extension of the maximum-weight matching problem which has applications in maximizing the number of patients matched to donors in kidney transplants.
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
327329-2006
Name nom
Cheung, Kevin
Department département
Mathematics and Statistics, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
20000
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
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
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
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
Solution methods and bounding techniques for hard combinatorial optimization problems
Keyword
NA
Application summary
When solving large-scale discrete optimization problems (that is, problems in which the decision variables represent indivisible quantities), one often finds good solutions using heuristics or approximation algorithms.  One way to measure the quality of a computed solution is by comparing its cost with a lower bound (in the case of minimization) obtained by solving a relaxation of the problem.  Having such a lower bound can be invaluable as it gives information on how far away from optimality the computed solution is.  The quality of such a bound is often critical to the performance of enumerative methods such as branch and bound. The proposed research has two related directions.  The first direction is to develop theoretical and empirical techniques for analyzing the quality of a relaxation of a discrete optimization problem.  Over the years, theoretical guarantees on how good certain relaxations approximate particular problems have been obtained.  Yet many of the analyses are problem-specific and are not readily transferrable to other problems.  The development of a general technique will permit a more systematic analysis of relaxations.  The second direction is to obtain a better understanding of what are commonly known as lift-and-project methods.  These methods can be used to obtain arbitrarily strong relaxations but the difficulty is that if used directly, they incur much computation overhead in practice.  The proposed research will study how to exploit problem structure and symmetry so that these methods can be applied in practice to problems that are known to be computationally challenging.  Problems studied will include the travelling tournament problem which has immediate applications in sports scheduling and an extension of the maximum-weight matching problem which has applications in maximizing the number of patients matched to donors in kidney transplants.