Grant: Discovery Grants Program - Individual
Concordia University
$30,000.00
Branching rules and resolution search in combinatorial optimization
FY 2012-13
Summary
Planning and scheduling problems are solved by methods of combinatorial optimization. These fall mainly in one of two categories: local search heuristics and so-called (for the contrast) exact algorithms. The umbrella of local search comprises heuristics aimed at quickly finding a reasonably good solution. Starting from such a solution, the exact algorithms proceed, often through a lot of hard work, to find the best solution and to prove that it is indeed the best. Heuristics have been the subject of intensive study by researchers in constraint satisfaction programming (often classified under ""artifical intelligence""); exact algorithms have been the subject of intensive study by researchers in mathematical programming (often classified under ""operations research""). Recent years have seen increasing interaction between these two initially separate communities, but the gap is still far from closed.
Many exact algorithms begin by splitting a problem into two or more subproblems, which are then solved separately. Branching rules are directions for choosing the split. Branching right is imperative for the efficiency of the overall solution process. The first part of the proposal aims to take a step towards a better understanding of branching strategies.
The second part of the proposal concerns refinements and testing of a combinatorial optimization algorithm called resolution search. This algorithm has been designed to
mitigate the harmful effect of bad branching decisions. In addition, it can act as a vehicle for bridging the gap between the heuristic algorithms and the exact algorithms.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
3333-2009
Name nom
Chv¦tal, Vasek
Department département
Computer Science and Software Engineering
Organization id
70
Institution établissement
Concordia University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2009
Award amount
30000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
4
Nb partie
5
Application title
Branching rules and resolution search in combinatorial optimization
Keyword
NSERC
Application summary
Planning and scheduling problems are solved by methods of combinatorial optimization. These fall mainly in one of two categories: local search heuristics and so-called (for the contrast) exact algorithms. The umbrella of local search comprises heuristics aimed at quickly finding a reasonably good solution. Starting from such a solution, the exact algorithms proceed, often through a lot of hard work, to find the best solution and to prove that it is indeed the best. Heuristics have been the subject of intensive study by researchers in constraint satisfaction programming (often classified under ""artifical intelligence""); exact algorithms have been the subject of intensive study by researchers in mathematical programming (often classified under ""operations research""). Recent years have seen increasing interaction between these two initially separate communities, but the gap is still far from closed.
Many exact algorithms begin by splitting a problem into two or more subproblems, which are then solved separately. Branching rules are directions for choosing the split. Branching right is imperative for the efficiency of the overall solution process. The first part of the proposal aims to take a step towards a better understanding of branching strategies.
The second part of the proposal concerns refinements and testing of a combinatorial optimization algorithm called resolution search. This algorithm has been designed to
mitigate the harmful effect of bad branching decisions. In addition, it can act as a vehicle for bridging the gap between the heuristic algorithms and the exact algorithms.