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,...
