IDEAS home Printed from https://ideas.repec.org/p/hal/wpaper/hal-00987708.html
   My bibliography  Save this paper

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

Author

Listed:
  • Laurent Alfandari

    (ESSEC Business School)

  • Agnès Plateau

    (CEDRIC - Centre d'études et de recherche en informatique et communications - ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise - CNAM - Conservatoire National des Arts et Métiers [CNAM])

  • Xavier Schepler

    (LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes - ULH - Université Le Havre Normandie - NU - Normandie Université - UNIROUEN - Université de Rouen Normandie - NU - Normandie Université - INSA Rouen Normandie - Institut national des sciences appliquées Rouen Normandie - INSA - Institut National des Sciences Appliquées - NU - Normandie Université)

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.

Suggested Citation

  • Laurent Alfandari & Agnès Plateau & Xavier Schepler, 2014. "A Branch-and-Price-and-Cut approach for Sustainable Crop Rotation Planning," Working Papers hal-00987708, HAL.
    • Handle: RePEc:hal:wpaper:hal-00987708
    Note: View the original document on HAL open archive server: https://essec.hal.science/hal-00987708
    as

    Download full text from publisher

    File URL: https://essec.hal.science/hal-00987708/document
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    2. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1998. "Lifted Cover Inequalities for 0-1 Integer Programs: Computation," INFORMS Journal on Computing, INFORMS, vol. 10(4), pages 427-437, November.
    3. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    4. L. Alfandari & J. Lemalade & A. Nagih & G. Plateau, 2011. "A MIP flow model for crop-rotation planning in a context of forest sustainable development," Annals of Operations Research, Springer, vol. 190(1), pages 149-164, October.
    5. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    6. Lana dos Santos & Philippe Michelon & Marcos Arenales & Ricardo Santos, 2011. "Crop rotation scheduling with adjacency constraints," Annals of Operations Research, Springer, vol. 190(1), pages 165-180, October.
    7. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    8. David Tilman & Kenneth G. Cassman & Pamela A. Matson & Rosamond Naylor & Stephen Polasky, 2002. "Agricultural sustainability and intensive production practices," Nature, Nature, vol. 418(6898), pages 671-677, August.
    9. dos Santos, Lana Mara R. & Costa, Alysson M. & Arenales, Marcos N. & Santos, Ricardo Henrique S., 2010. "Sustainable vegetable crop supply problem," European Journal of Operational Research, Elsevier, vol. 204(3), pages 639-647, August.
    10. Detlefsen, Nina K. & Jensen, Allan Leck, 2007. "Modelling optimal crop sequences using network flows," Agricultural Systems, Elsevier, vol. 94(2), pages 566-572, May.
    11. Talaat El-Nazer & Bruce A. McCarl, 1986. "The Choice of Crop Rotation: A Modeling Approach and Case Study," American Journal of Agricultural Economics, Agricultural and Applied Economics Association, vol. 68(1), pages 127-136.
    12. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    13. Haneveld, W. K. Klein & Stegeman, A. W., 2005. "Crop succession requirements in agricultural production planning," European Journal of Operational Research, Elsevier, vol. 166(2), pages 406-429, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alfandari, Laurent & Plateau, Agnès & Scheplerc, Xavier, 2014. "A Branch-and-Price-and-Cut Approach for Sustainable Crop Rotation Planning," ESSEC Working Papers WP1408, ESSEC Research Center, ESSEC Business School.
    2. Alfandari, Laurent & Plateau, Agnès & Schepler, Xavier, 2015. "A branch-and-price-and-cut approach for sustainable crop rotation planning," European Journal of Operational Research, Elsevier, vol. 241(3), pages 872-879.
    3. repec:hal:journl:hal-00987708 is not listed on IDEAS
    4. Santos, Lana M.R. & Munari, Pedro & Costa, Alysson M. & Santos, Ricardo H.S., 2015. "A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes," European Journal of Operational Research, Elsevier, vol. 245(2), pages 581-590.
    5. Alysson Costa & Lana Santos & Douglas Alem & Ricardo Santos, 2014. "Sustainable vegetable crop supply problem with perishable stocks," Annals of Operations Research, Springer, vol. 219(1), pages 265-283, August.
    6. dos Santos, Lana Mara R. & Costa, Alysson M. & Arenales, Marcos N. & Santos, Ricardo Henrique S., 2010. "Sustainable vegetable crop supply problem," European Journal of Operational Research, Elsevier, vol. 204(3), pages 639-647, August.
    7. Víctor M. Albornoz & Gabriel E. Zamora, 2021. "Decomposition-based heuristic for the zoning and crop planning problem with adjacency constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 248-265, April.
    8. Jitka JANOVÁ, 2014. "Crop plan optimization under risk on a farm level in the Czech Republic," Agricultural Economics, Czech Academy of Agricultural Sciences, vol. 60(3), pages 123-132.
    9. Kristiansen, Simon & Sørensen, Matias & Stidsen, Thomas R., 2011. "Elective course planning," European Journal of Operational Research, Elsevier, vol. 215(3), pages 713-720, December.
    10. Panagiotis Andrianesis & Dimitris Bertsimas & Michael C. Caramanis & William W. Hogan, 2020. "Computation of Convex Hull Prices in Electricity Markets with Non-Convexities using Dantzig-Wolfe Decomposition," Papers 2012.13331, arXiv.org, revised Oct 2021.
    11. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    12. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    13. Gondzio, Jacek & González-Brevis, Pablo & Munari, Pedro, 2013. "New developments in the primal–dual column generation technique," European Journal of Operational Research, Elsevier, vol. 224(1), pages 41-51.
    14. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    15. Allman, Andrew & Zhang, Qi, 2020. "Dynamic location of modular manufacturing facilities with relocation of individual modules," European Journal of Operational Research, Elsevier, vol. 286(2), pages 494-507.
    16. Angelo Aliano Filho & Helenice Oliveira Florentino & Margarida Vaz Pato & Sônia Cristina Poltroniere & João Fernando Silva Costa, 2022. "Exact and heuristic methods to solve a bi-objective problem of sustainable cultivation," Annals of Operations Research, Springer, vol. 314(2), pages 347-376, July.
    17. Víctor M. Albornoz & Marcelo I. Véliz & Rodrigo Ortega & Virna Ortíz-Araya, 2020. "Integrated versus hierarchical approach for zone delineation and crop planning under uncertainty," Annals of Operations Research, Springer, vol. 286(1), pages 617-634, March.
    18. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    19. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    20. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    21. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.

    More about this item

    Keywords

    OR in agriculture; crop rotations; production planning; column generation; branch-and-price-and-cut;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:wpaper:hal-00987708. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.