A Branch-and-Price-and-Cut approach for Sustainable Crop Rotation Planning

Abstract : In this paper, we study a multi-periodic production planning problem in agriculture. This problem belongs to the class of crop rotation planning problems, which have received increased attention in the literature in recent years. Crop cultivation and fallow periods must be scheduled on land plots over a given time horizon so as to minimize the total surface area of land used, while satisfying crop demands every period. This problem is proven strongly NP-hard. We propose a 0-1 linear programming compact formulation based on crop-sequence graphs. An extended formulation is then provided with a polynomial-time pricing problem, and a Branch-and-Priceand- Cut (BPC) algorithm is presented with adapted branching rules and cutting planes. The numerical experiments on instances varying the number of crops, periods and plots show the effectiveness of the BPC for the extended formulation compared to solving the compact formulation, even though these two formulations have the same linear relaxation bound.
Type de document :
Pré-publication, Document de travail
ESSEC Working paper. Document de Recherche ESSEC / Centre de recherche de l’ESSEC. ISSN : 1291-9616. WP 1408. 2014. 2014
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-essec.archives-ouvertes.fr/hal-00987708
Contributeur : Michel Demoura <>
Soumis le : mardi 6 mai 2014 - 16:34:49
Dernière modification le : mardi 10 juillet 2018 - 17:02:03
Document(s) archivé(s) le : lundi 10 avril 2017 - 19:47:17

Fichier

WP1408.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00987708, version 1

Citation

Laurent Alfandari, Agnès Plateau, Xavier Schepler. A Branch-and-Price-and-Cut approach for Sustainable Crop Rotation Planning. ESSEC Working paper. Document de Recherche ESSEC / Centre de recherche de l’ESSEC. ISSN : 1291-9616. WP 1408. 2014. 2014. 〈hal-00987708〉

Partager

Métriques

Consultations de la notice

320

Téléchargements de fichiers

407