Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$20,000.00
Solving rich and integrated decision problems with hybrid operations research and constraint programming approaches
FY 2011-12
Summary
In recent decades, decision support systems and optimization software have generated huge savings while significantly increasing the productivity of organizations in Canada and around the world. Commercial software packages based on Operations Research (OR) technologies have been able to produce near optimal solutions to many of the difficult problems faced by modern industries. Airline demand forecasting, fleet sizing, flight scheduling, crew scheduling and rostering, and aircraft routing are examples of some of the areas which have benefited. Typically, each of the these problems has been addressed separately and in sequence, with outputs from the first problems solved serving as inputs to those coming later. This sequential and sometimes simplified approach allowed researchers to understand the individual problems and develop effective methodologies to address them, but the process can be somewhat myopic since optimal global decision-making is not specifically addressed. Even though the integration of all levels of decisions in order to model the complete problem is in most cases impossible or impractical, progress toward that end should in many cases yield additional cost savings and gains in productivity. The main obstacle to realising the potential additional benefits of integrated decision making lies in the structural differences which exist among the models used to address different parts of the overall problem. Algorithms developed to optimize parts of the global problem cannot simply be merged together. The proposed research program thus aims at making significant progress toward solving rich integrated decision problems by proposing new methodologies based on hybridizing traditional operations research approaches and Constraint Programming (CP) techniques. CP concentrate on the feasibility of a solution; logical inference and filtering techniques are used to discard quickly those partial solutions which can be shown to be infeasible, even though the majority of the variables are still unassigned. The combination of CP's modeling flexibility and its emphasis on feasibility together with OR's optimization efficiency offers the promise of decision tools that are both powerful and versatile.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
288209-2009
Name nom
Rousseau, LouisMartin
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2009
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
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
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
Solving rich and integrated decision problems with hybrid operations research and constraint programming approaches
Keyword
NSERC
Application summary
In recent decades, decision support systems and optimization software have generated huge savings while significantly increasing the productivity of organizations in Canada and around the world. Commercial software packages based on Operations Research (OR) technologies have been able to produce near optimal solutions to many of the difficult problems faced by modern industries. Airline demand forecasting, fleet sizing, flight scheduling, crew scheduling and rostering, and aircraft routing are examples of some of the areas which have benefited. Typically, each of the these problems has been addressed separately and in sequence, with outputs from the first problems solved serving as inputs to those coming later. This sequential and sometimes simplified approach allowed researchers to understand the individual problems and develop effective methodologies to address them, but the process can be somewhat myopic since optimal global decision-making is not specifically addressed. Even though the integration of all levels of decisions in order to model the complete problem is in most cases impossible or impractical, progress toward that end should in many cases yield additional cost savings and gains in productivity. The main obstacle to realising the potential additional benefits of integrated decision making lies in the structural differences which exist among the models used to address different parts of the overall problem. Algorithms developed to optimize parts of the global problem cannot simply be merged together. The proposed research program thus aims at making significant progress toward solving rich integrated decision problems by proposing new methodologies based on hybridizing traditional operations research approaches and Constraint Programming (CP) techniques. CP concentrate on the feasibility of a solution; logical inference and filtering techniques are used to discard quickly those partial solutions which can be shown to be infeasible, even though the majority of the variables are still unassigned. The combination of CP's modeling flexibility and its emphasis on feasibility together with OR's optimization efficiency offers the promise of decision tools that are both powerful and versatile.