Two-dimensional knapsack-block packing problem

2019 
Abstract We study the two-dimensional knapsack problem with block packing constraints that is originated from an agricultural company when placing its seed experiments into test fields. The problem extends the classical knapsack problem by considering a block packing requirement. In this problem, a single bin is divided into many disjoint blocks and each block is a union of rectangles. If an item is placed, it should be contained in one of the blocks. The objective is to select a subset of the items to be packed into the bin to maximize the space usage, or equivalently, to minimize the wasted space. We propose three types of mathematical models for addressing the problem. The efficiency of the proposed models is analyzed through numerical studies.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    37
    References
    1
    Citations
    NaN
    KQI
    []