EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

675. Exact Mixed-Integer and Constraint Programming solutions to the two-dimensional bin packing problem with due dates

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. Milad Dehghan
Information Technology, Deakin University
2. Sergey Polyakovskiy
Deakin University

Abstract

The two-dimensional non-oriented bin packing problem with due dates consists in packing a set of rectangular items, which may be rotated by 90 degrees, into identical rectangular bins. The bins have equal processing times. The problem searches for a feasible layout of items so as to minimize the maximum lateness, with the lateness of each item being the difference between its due date and the completion time of its assigned bin. This minimax problem is computationally challenging: It has a huge solution space with many alternative solutions whose packing configurations are either symmetric or lead to the same solution cost.

We propose two exact approaches. First, we solve the problem as a mixed-integer program (MIP), which we strengthen with a set of feasibility and symmetry-breaking constraints. Our second solution employs constraint programming (CP), and thus benefits from the strength of cumulative scheduling relaxations of the packing problem. Our extensive computational experiments show that MIP, which stands as a more traditional modelling technique within the cutting and packing community, is only successful on small-sized benchmark instances with as few as 60 items. It is outperformed by CP that can solve medium and large instances with up to 100 items in a reasonable time.

Keywords

Status: accepted

Back to the list of papers