Reference number : GC-2017-Q1-02876, amendment number : , agreement type : G, recipient legal name : Soumis, François (École Polytechnique de Montréal), recipient country : CA, recipient province : nan, recipient city : Quebec|Québec, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : Depuis 35 ans mon &eacute;quipe a d&eacute;velopp&eacute; le savoir-faire sur l'application industrielle de la g&eacute;n&eacute;ration de colonnes qui permet de consid&eacute;rer seulement un nombre r&eacute;duit de variables &agrave; la fois. Ceci a permis de d&eacute;velopper GENCOL le premier algorithme optimal pour les horaires de pilotes d&rsquo;avion et les conducteurs d&rsquo;autobus. Des r&eacute;ductions de co&ucirc;ts de l&rsquo;ordre de 5% ont donn&eacute; l&rsquo;avantage comp&eacute;titif &agrave; Giro et AD OPT et permis leur croissance au niveau mondial. Les recherches ont aussi port&eacute; sur la r&eacute;duction dynamique de l&rsquo;ensemble des contraintes &agrave; consid&eacute;rer simultan&eacute;ment et l&rsquo;&eacute;limination temporaire de variables (algorithme IPS). Il a permis de traiter les probl&egrave;mes de rotations d&rsquo;&eacute;quipages a&eacute;riens une semaine &agrave; la fois (10 000 vols) plut&ocirc;t qu&rsquo;une journ&eacute;e type et une autre r&eacute;duction de co&ucirc;t de l&rsquo;ordre de 5%. 
Un premier objectif porte sur l&rsquo;algorithme ISUD un simplexe en nombres entiers. Il commence avec une solution enti&egrave;re et produit une suite de solutions qui s&rsquo;am&eacute;liorent jusqu&rsquo;&agrave; atteindre une solution optimale. Il utilise aussi l&rsquo;agr&eacute;gation de contraintes et l&rsquo;&eacute;limination de variables comme IPS. Des probl&egrave;mes de chauffeurs d&rsquo;autobus et de pilotes d&rsquo;avion de 500 000 variables ont &eacute;t&eacute; r&eacute;solus, dans 95% des cas, beaucoup plus rapidement qu&rsquo;avec CPLEX un des meilleurs logiciels de Branch and Bound. Il faut d&eacute;velopper de nouvelles id&eacute;es pour traiter le 5% qui reste et ajouter la g&eacute;n&eacute;ration de colonnes pour traiter de plus grands probl&egrave;mes. On vise les probl&egrave;mes mensuels de 50 000 vols. 
Un second objectif de recherche sera de d&eacute;velopper un syst&egrave;me utilisant l&rsquo;intelligence artificielle (IA) pour estimer la probabilit&eacute; que les arcs entre deux t&acirc;ches fassent partie de la solution d&rsquo;un probl&egrave;me de rotations d&rsquo;&eacute;quipages a&eacute;riens. Cette information sera utilis&eacute;e par IPS et ISUD pour agr&eacute;ger les taches et &eacute;liminer des arcs pour acc&eacute;l&eacute;rer les algorithmes. 
Finalement, poursuivre la recherche fondamentale et le d&eacute;veloppement du savoir-faire sur l'application industrielle de la d&eacute;composition de Benders. Nous l&rsquo;appliquons &agrave; l&rsquo;int&eacute;gration des probl&egrave;mes de rotations d&rsquo;&eacute;quipage et de blocs mensuels. C&rsquo;est une d&eacute;composition de Benders ou le probl&egrave;me ma&icirc;tre et le sous-probl&egrave;me sont r&eacute;solus par g&eacute;n&eacute;ration de colonnes. Dans cette d&eacute;composition avec quatre niveaux, il faut r&eacute;partir l&rsquo;effort de calcul entre les niveaux pour ne pas mettre beaucoup de temps pour faire de petites am&eacute;liorations &agrave; un niveau quand il y en a de grosses &agrave; faire ailleurs. Les coupes de Benders transf&eacute;rant de l&rsquo;information du probl&egrave;me de blocs mensuels au probl&egrave;me de rotations sont construites avec une solution duale du probl&egrave;me de blocs. Il y a un nombre extr&ecirc;mement grand de solutions duales dans ce probl&egrave;me. Nous proposons un probl&egrave;me d&rsquo;optimisation pour choisir une solution qui est centrale pour stabiliser le processus., program purpose french : Depuis 35 ans mon &eacute;quipe a d&eacute;velopp&eacute; le savoir-faire sur l'application industrielle de la g&eacute;n&eacute;ration de colonnes qui permet de consid&eacute;rer seulement un nombre r&eacute;duit de variables &agrave; la fois. Ceci a permis de d&eacute;velopper GENCOL le premier algorithme optimal pour les horaires de pilotes d&rsquo;avion et les conducteurs d&rsquo;autobus. Des r&eacute;ductions de co&ucirc;ts de l&rsquo;ordre de 5% ont donn&eacute; l&rsquo;avantage comp&eacute;titif &agrave; Giro et AD OPT et permis leur croissance au niveau mondial. Les recherches ont aussi port&eacute; sur la r&eacute;duction dynamique de l&rsquo;ensemble des contraintes &agrave; consid&eacute;rer simultan&eacute;ment et l&rsquo;&eacute;limination temporaire de variables (algorithme IPS). Il a permis de traiter les probl&egrave;mes de rotations d&rsquo;&eacute;quipages a&eacute;riens une semaine &agrave; la fois (10 000 vols) plut&ocirc;t qu&rsquo;une journ&eacute;e type et une autre r&eacute;duction de co&ucirc;t de l&rsquo;ordre de 5%. 
Un premier objectif porte sur l&rsquo;algorithme ISUD un simplexe en nombres entiers. Il commence avec une solution enti&egrave;re et produit une suite de solutions qui s&rsquo;am&eacute;liorent jusqu&rsquo;&agrave; atteindre une solution optimale. Il utilise aussi l&rsquo;agr&eacute;gation de contraintes et l&rsquo;&eacute;limination de variables comme IPS. Des probl&egrave;mes de chauffeurs d&rsquo;autobus et de pilotes d&rsquo;avion de 500 000 variables ont &eacute;t&eacute; r&eacute;solus, dans 95% des cas, beaucoup plus rapidement qu&rsquo;avec CPLEX un des meilleurs logiciels de Branch and Bound. Il faut d&eacute;velopper de nouvelles id&eacute;es pour traiter le 5% qui reste et ajouter la g&eacute;n&eacute;ration de colonnes pour traiter de plus grands probl&egrave;mes. On vise les probl&egrave;mes mensuels de 50 000 vols. 
Un second objectif de recherche sera de d&eacute;velopper un syst&egrave;me utilisant l&rsquo;intelligence artificielle (IA) pour estimer la probabilit&eacute; que les arcs entre deux t&acirc;ches fassent partie de la solution d&rsquo;un probl&egrave;me de rotations d&rsquo;&eacute;quipages a&eacute;riens. Cette information sera utilis&eacute;e par IPS et ISUD pour agr&eacute;ger les taches et &eacute;liminer des arcs pour acc&eacute;l&eacute;rer les algorithmes. 
Finalement, poursuivre la recherche fondamentale et le d&eacute;veloppement du savoir-faire sur l'application industrielle de la d&eacute;composition de Benders. Nous l&rsquo;appliquons &agrave; l&rsquo;int&eacute;gration des probl&egrave;mes de rotations d&rsquo;&eacute;quipage et de blocs mensuels. C&rsquo;est une d&eacute;composition de Benders ou le probl&egrave;me ma&icirc;tre et le sous-probl&egrave;me sont r&eacute;solus par g&eacute;n&eacute;ration de colonnes. Dans cette d&eacute;composition avec quatre niveaux, il faut r&eacute;partir l&rsquo;effort de calcul entre les niveaux pour ne pas mettre beaucoup de temps pour faire de petites am&eacute;liorations &agrave; un niveau quand il y en a de grosses &agrave; faire ailleurs. Les coupes de Benders transf&eacute;rant de l&rsquo;information du probl&egrave;me de blocs mensuels au probl&egrave;me de rotations sont construites avec une solution duale du probl&egrave;me de blocs. Il y a un nombre extr&ecirc;mement grand de solutions duales dans ce probl&egrave;me. Nous proposons un probl&egrave;me d&rsquo;optimisation pour choisir une solution qui est centrale pour stabiliser le processus., agreement title english : Nouvelles méthodes d'optimisation mathématiques pour les grands problèmes d'horaires de véhicules et de personnel, agreement title french : Nouvelles méthodes d'optimisation mathématiques pour les grands problèmes d'horaires de véhicules et de personnel, agreement number : RGPIN, agreement value : 355000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada