Program > By speacker > Alfandari Laurent

Les problèmes de contruction de rotations agricoles connaissent un essor important dans la littérature depuis les cinq dernières années, notamment dans un objectif de développement durable. Nous nous intéressons ici à un problème spécifique de minimisation de l'espace agricole requis pour couvrir des demandes saisonnières en diverses cultures, dans un contexte de tension sur les ressources foncières. Une rotation alterne des périodes de culture et de jachère sur un horizon de temps et sur une parcelle de taille donnée, avec des rendements croissants en fonction de la durée de la dernière jachère et décroissants en fonction de la durée de culture. Nous montrons que le problème est NP-difficile au sens fort par réduction avec le problème de couverture d'ensemble. Nous introduisons une formulation compacte du problème de type flot multi-commodités avec variables arcs, sur la base d'un graphe de séquences multi-états associé à chaque parcelle. Nous proposons ensuite une formulation étendue de type Covering Integer Programming, issue d'une décomposition Dantzig-Wolfe. La relaxation continue de cette formulation étendue est résolue par génération de colonnes. Un sous-problème de pricing polynomial est associé à chaque parcelle, résolu par programmation dynamique. Cette résolution par génération de colonnes du problème maître est intégrée à un algorithme de branch-and-price-and-cut, avec règles de branchement et plans coupants adaptés à la structure du problème. L'originalité de cette communication réside dans la définition du problème et l'application de cette technique de branch-and-price-and-cut (BPC) alors qu'à notre connaissance, ni branch-and-price ni branch-and-cut n'avaient été appliqués auparavant à un problème de construction de rotations agricoles, au-delà de quelques papiers existants utilisant la génération de colonnes. La méthode proposée fournit d'excellents résultats sur des instances faisant varier le nombre de cultures, l'horizon de temps et la taille des parcelles. Pour les petites instances le BPC fournit la meilleure solution pour la totalité des 20 instances, contre 17/20 pour la résolution directe de la formulation compacte, avec des temps réduits en cas d'égalité. Pour les instances plus difficiles avec un temps limite de 3600s, le BPC fournit la meilleure solution pour 23 des 30 instances, contre 7/30 pour la formulation compacte. Ce résultat est obtenu malgré l'égalité de la borne LP entre les deux formulations. Enfin, un apport du papier est de confirmer un résultat théorique que plus le morcellement des parcelles est important, plus l'espace requis pour couvrir les demandes à l'optimum est réduit, la taille des parcelles étant donc un paramètre critique non seulement pour la résolution du problème mais aussi pour l'objectif de développement durable.