EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

949. Primal and Dual Bounds to the Variable-Sized Two-Dimensional Guillotine Bin Packing Problem

Invited abstract in session MA-7: Cutting and Packing 1 - 2D rectangular, stream Cutting and Packing (ESICUP).

Monday, 8:30-10:00
Room: 1019 (building: 202)

Authors (first author is the speaker)

1. Adam McGregor
School of Information Technology, Deakin University
2. Sergey Polyakovskiy
Deakin University

Abstract

Given a set of small rectangular items and large non-identical rectangular bins, the variable-sized two-dimensional guillotine bin packing problem searches for a feasible packing of the items into the bins, with the items obtained via guillotine cuts. It minimises the total cost of the used bins. We propose a hybrid column generation based matheuristic that solves the problem approximately. Its reduced master problem, which is solved as an integer program, is the classical Dantzig-Wolfe formulation of the VS2BP. The master problem uses a collection of feasible packings that are constructed heuristically during the search process. The initial set of packings is obtained via a heuristic, which selects and packs bins sequentially. This warm-start heuristic employs a look-ahead mechanism that prohibits the search of infeasible directions and enforces directions of likely advance, halting only after the allocated time expires. After this, the incumbent is enhanced by solving a series of pricing problems for each bin type by finding a feasible packing with the largest reduced cost, providing extra columns for the master problem. The search ends either when no solution to the pricing problem is found or when time expires. The packing process is done approximately via an algorithm that hybridizes constraint programming with a heuristic search. Extensive computational experiments provide evidence of good performance of the proposed approach, when compared to the state of the art.

Keywords

Status: accepted

Back to the list of papers