Un algorithme de Branch-and-Price pour le problème de planification durable de rotations culturales

International audienceNous nous intéressons à une application de la Recherche Opérationnelle à l?agriculture : le problème de planification durable des rotations culturales. Ce problème, défini dans [4] et dont une variante a été initialement introduite dans [1], consiste à couvrir des demandes saisonnières en diverses cultures sur un horizon de temps donné, tout en minimisant l?espace agricole requis. La rotation culturale est une pratique qui consiste à alterner des périodes de cultures et de jachères et permet de maintenir des rendements satisfaisants avec des engrais naturels en préservant les sols. Dans le problème considéré ici, l?espace agricole est divisé en parcelles de taille identique, et l?objectif revient à minimiser le nombre de parcelles utilisées en associant à chacune d?elles un plan de rotations culturales sur l?horizon fixé. Le problème est noté MSCRP (Minimum Space Crop Rotation Planning). Contrairement à [1], nous n?imposons pas de recultiver la parcelle après un certain nombre de périodes de jachère, et les variables de production sont binaires, i.e., à une période donnée, soit la parcelle est complètement cultivée d?une seule et même culture, soit elle est en jachère. Nous démontrons la NP-complétude du problème MSCRP. Nous proposons ensuite une formulation de type Programmation Linéaire en Variables 0-1, plus compacte que le modèle présenté dans [1] et [4]. Une décomposition de type Dantzig-Wolfe [3] est introduite pour résoudre la relaxation linéaire du problème par génération de colonnes, et un algorithme de branch-and-price [2, 5] est présenté. Un schéma de branchement basé sur le théorème de décomposition des flots est introduit. Nous introduisons également des coupes valides de type knapsack. Finalement, nous montrons l?efficacité de la méthode par des résultats numériques sur des instances générées aléatoirement