IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v74y2019i1d10.1007_s10898-019-00741-w.html
   My bibliography  Save this article

On three soft rectangle packing problems with guillotine constraints

Author

Listed:
  • Quoc Trung Bui

    (Daily-Opt Joint Stock Company
    FPT University
    Vietnam Technological and Commercial Joint Stock Bank)

  • Thibaut Vidal

    (Pontifícia Universidade Católica do Rio de Janeiro)

  • Minh Hoàng Hà

    (Vietnam National University)

Abstract

We investigate how to partition a rectangular region of length $$L_1$$ L 1 and height $$L_2$$ L 2 into n rectangles of given areas $$(a_1, \dots , a_n)$$ ( a 1 , ⋯ , a n ) using two-stage guillotine cuts, so as to minimize either (i) the sum of the perimeters, (ii) the largest perimeter, or (iii) the maximum aspect ratio of the rectangles. These problems play an important role in the ongoing Vietnamese land-allocation reform, as well as in the optimization of matrix multiplication algorithms. We show that the first problem can be solved to optimality in $${{\mathcal {O}}}(n \log n)$$ O ( n log n ) , while the two others are NP-hard. We propose mixed integer linear programming formulations and a binary search-based approach for solving the NP-hard problems. Experimental analyses are conducted to compare the solution approaches in terms of computational efficiency and solution quality, for different objectives.

Suggested Citation

  • Quoc Trung Bui & Thibaut Vidal & Minh Hoàng Hà, 2019. "On three soft rectangle packing problems with guillotine constraints," Journal of Global Optimization, Springer, vol. 74(1), pages 45-62, May.
    • Handle: RePEc:spr:jglopt:v:74:y:2019:i:1:d:10.1007_s10898-019-00741-w
    DOI: 10.1007/s10898-019-00741-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00741-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00741-w?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. Arimoto, Yutaka, 2010. "Impact of land readjustment project on farmland use and structural adjustment: The case of Niigata, Japan," 2010 Annual Meeting, July 25-27, 2010, Denver, Colorado 61278, Agricultural and Applied Economics Association.
    2. Paes, Frederico Galaxe & Pessoa, Artur Alves & Vidal, Thibaut, 2017. "A hybrid genetic algorithm with decomposition phases for the Unequal Area Facility Layout Problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 742-756.
    3. Pham Van Hung & T. Gordon MacAulay & Sally P. Marsh, 2007. "The economics of land fragmentation in the north of Vietnam ," Australian Journal of Agricultural and Resource Economics, Australian Agricultural and Resource Economics Society, vol. 51(2), pages 195-211, June.
    4. Heltberg, Rasmus, 1998. "Rural market imperfections and the farm size-- productivity relationship: Evidence from Pakistan," World Development, Elsevier, vol. 26(10), pages 1807-1826, 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. Trung X. Hoang & Nga V. T. Le, 2021. "Natural disasters and risk aversion: Evidence from Vietnam," Natural Resources Forum, Blackwell Publishing, vol. 45(3), pages 211-229, August.
    2. Do, Manh Hung & Nguyen, Trung Thanh & Grote, Ulrike, 2023. "Land consolidation, rice production, and agricultural transformation: Evidence from household panel data for Vietnam," Economic Analysis and Policy, Elsevier, vol. 77(C), pages 157-173.
    3. Latruffe, Laure & Piet, Laurent, 2013. "Does land fragmentation affect farm performance? A case study from Brittany," Factor Markets Working Papers 151, Centre for European Policy Studies.
    4. Kawasaki, Kentaro, 2010. "The costs and benefits of land fragmentation of rice farms in Japan," Australian Journal of Agricultural and Resource Economics, Australian Agricultural and Resource Economics Society, vol. 54(4), pages 1-18.
    5. Klaus Deininger & Songqing Jin & Yanyan Liu & Sudhir K. Singh, 2018. "Can Labor-Market Imperfections Explain Changes in the Inverse Farm Size–Productivity Relationship? Longitudinal Evidence from Rural India," Land Economics, University of Wisconsin Press, vol. 94(2), pages 239-258.
    6. Longhui Meng & Liang Ding & Ray Tahir Mushtaq & Saqib Anwar & Aqib Mashood Khan, 2024. "Efficient Packing of 2D Irregular Parts: A Hybrid Approach Incorporating a Modified Genetic Algorithm and Image Processing," Mathematics, MDPI, vol. 12(22), pages 1-21, November.
    7. Yen H. T. Nguyen & Tuyen Q. Tran & Dung T. Hoang & Thu M. T. Tran & Trung T. Nguyen, 2023. "Land quality, income, and poverty among rural households in the North Central Region, Vietnam," Poverty & Public Policy, John Wiley & Sons, vol. 15(2), pages 150-172, June.
    8. Chen, Xuan & Vuong, Nguyen, 2018. "Climate and Off-farm Labor Supply of Agricultural Households: Evidence from Rural Vietnam," 2018 Annual Meeting, August 5-7, Washington, D.C. 274187, Agricultural and Applied Economics Association.
    9. Barati, Ali Akbar & Azadi, Hossein & Scheffran, Jürgen, 2021. "Agricultural land fragmentation in Iran: Application of game theory," Land Use Policy, Elsevier, vol. 100(C).
    10. Nguyen, Huy, 2014. "The effect of land fragmentation on labor allocation and the economic diversity of farm households: The case of Vietnam," MPRA Paper 57521, University Library of Munich, Germany.
    11. Tuyen Quang Tran & Huong Van Vu, 2021. "The impact of land fragmentation on food security in the North Central Coast, Vietnam," Asia and the Pacific Policy Studies, Wiley Blackwell, vol. 8(2), pages 327-345, May.
    12. Mariem Besbes & Marc Zolghadri & Roberta Costa Affonso & Faouzi Masmoudi & Mohamed Haddar, 2020. "A methodology for solving facility layout problem considering barriers: genetic algorithm coupled with A* search," Journal of Intelligent Manufacturing, Springer, vol. 31(3), pages 615-640, March.
    13. Vavra, Pavel & Colman, David, 2003. "The analysis of UK crop allocation at the farm level: implications for supply response analysis," Agricultural Systems, Elsevier, vol. 76(2), pages 697-713, May.
    14. Rizov, Marian, 2005. "Human capital and the agrarian structure in transition: Micro evidence from Romania," EconStor Open Access Articles and Book Chapters, ZBW - Leibniz Information Centre for Economics, vol. 26(1), pages 119-149.
    15. Thapa, Sridhar, 2007. "The relationship between farm size and productivity: empirical evidence from the Nepalese mid-hills," 106th Seminar, October 25-27, 2007, Montpellier, France 7940, European Association of Agricultural Economists.
    16. C.S.C. Sekhar, 2021. "Price or income support to farmers? Policy options and implications," IEG Working Papers 420, Institute of Economic Growth.
    17. Jan Fałkowski & Pavel Ciaian & d'Artis Kancs, 2009. "Access to Credit, Factor Allocation and Farm Productivity: Evidence From the CEE Transition Economies," Working Papers 2009-12, Faculty of Economic Sciences, University of Warsaw.
    18. Jiguang Zhu & Yaru Sun & Yunxing Song, 2022. "Household Livelihood Strategy Changes and Agricultural Diversification: A Correlation and Mechanism Analysis Based on Data from the China Family Panel," Land, MDPI, vol. 11(5), pages 1-18, May.
    19. Thi Ha Thanh Nguyen & Thi Quynh Nhu Thai & Van Tuan Tran & Thi Phin Pham & Quang Cuong Doan & Khac Hung Vu & Huong Giang Doan & Quang Thanh Bui, 2020. "Land Consolidation at the Household Level in the Red River Delta, Vietnam," Land, MDPI, vol. 9(6), pages 1-23, June.
    20. Nguyen, Quang & Kim, Doo-Chul, 2019. "Farmers’ landholding strategy in urban fringe areas: A case study of a transitional commune near Ho Chi Minh City, Vietnam," Land Use Policy, Elsevier, vol. 83(C), pages 95-104.

    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:spr:jglopt:v:74:y:2019:i:1:d:10.1007_s10898-019-00741-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.