IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v241y2015i3p872-879.html
   My bibliography  Save this article

A branch-and-price-and-cut approach for sustainable crop rotation planning

Author

Listed:
  • Alfandari, Laurent
  • Plateau, Agnès
  • Schepler, Xavier

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 considerable 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 formulation based on crop-sequence graphs. An extended formulation is then provided with a polynomial-time pricing problem, and a Branch-and-Price-and-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

  • 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.
    • Handle: RePEc:eee:ejores:v:241:y:2015:i:3:p:872-879
    DOI: 10.1016/j.ejor.2014.09.066
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714008558
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.09.066?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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. Detlefsen, Nina K. & Jensen, Allan Leck, 2007. "Modelling optimal crop sequences using network flows," Agricultural Systems, Elsevier, vol. 94(2), pages 566-572, May.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    9. 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.
    10. 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.
    11. 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.
    12. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    13. 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.
    14. 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.
    15. Marius Rădulescu & Constanta Rădulescu & Gheorghiţă Zbăganu, 2014. "A portfolio theory approach to crop planning under environmental constraints," Annals of Operations Research, Springer, vol. 219(1), pages 243-264, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Regis Mauri, Geraldo, 2019. "Improved mathematical model and bounds for the crop rotation scheduling problem with adjacency constraints," European Journal of Operational Research, Elsevier, vol. 278(1), pages 120-135.
    2. 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.
    3. Schepler, Xavier & Rossi, André & Gurevsky, Evgeny & Dolgui, Alexandre, 2022. "Solving robust bin-packing problems with a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 831-843.
    4. 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.
    5. Ernst-August Nuppenau, 2018. "Soil Fertility Management by Transition Matrices and Crop Rotation: On Spatial and Dynamic Aspects in Programming of Ecosystem Services," Sustainability, MDPI, vol. 10(7), pages 1-20, June.
    6. 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.
    7. Mariana Escallón-Barrios & Daniel Castillo-Gomez & Jorge Leal & Carlos Montenegro & Andrés L. Medaglia, 2022. "Improving harvesting operations in an oil palm plantation," Annals of Operations Research, Springer, vol. 314(2), pages 411-449, July.
    8. Yuanhe Yu & Liang Wang & Jinkuo Lin & Zijun Li, 2022. "Optimizing Agricultural Input and Production for Different Types of at-Risk Peasant Households: An Empirical Study of Typical Counties in the Yimeng Mountain Area of Northern China," IJERPH, MDPI, vol. 19(21), pages 1-22, October.
    9. Ana Esteso & M. M. E. Alemany & Angel Ortiz & Shaofeng Liu, 2022. "Optimization model to support sustainable crop planning for reducing unfairness among farmers," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(3), pages 1101-1127, September.
    10. Pagare, Dewang & Biswas, Indranil & Agrahari, Amit & Ghosh, Sriparna, 2023. "A small farmer’s market choice in the presence of multiple markets: The Indian case," European Journal of Operational Research, Elsevier, vol. 311(2), pages 739-753.
    11. Ruslan Sadykov & François Vanderbeck & Artur Pessoa & Issam Tahiri & Eduardo Uchoa, 2019. "Primal Heuristics for Branch and Price: The Assets of Diving Methods," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 251-267, April.
    12. Salvatore Ammirato & Alberto Michele Felicetti & Massimiliano Ferrara & Cinzia Raso & Antonio Violi, 2021. "Collaborative Organization Models for Sustainable Development in the Agri-Food Sector," Sustainability, MDPI, vol. 13(4), pages 1-22, February.

    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. 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.
    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. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    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. Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
    16. 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.
    17. 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.
    18. 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.
    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. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.

    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:eee:ejores:v:241:y:2015:i:3:p:872-879. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.