EUROPT 2024
Abstract Submission

278. The Bin Packing Problem with Setups: properties and formulations

Invited abstract in session WE-7: Optimization applications III, stream Optimization applications.

Wednesday, 14:10 - 15:50
Room: M:I

Authors (first author is the speaker)

1. Fabio Ciccarelli
Department of computer, control and management engineering (DIAG), Sapienza University of Rome
2. Roberto Baldacci
College of Science and Engineering, Hamad Bin Khalifa University
3. Stefano Coniglio
Department of Economics, University of Bergamo
4. Fabio Furini
DIAG, La Sapienza

Abstract

In this work, we introduce a novel extension to the classical Bin Packing Problem (BPP), the Bin Packing Problem with Setups (BPPS), in which items are partitioned into classes with associated setup weights and costs. The objective is therefore to find an optimal packing, i.e., a solution that minimizes the sum of bins and setup costs. The BPPS presents a complex extension of the traditional Bin Packing Problem, and it holds significant implications across various logistical and industrial domains.

We explore different possible formulations for the BPPS, investigating their theoretical properties and conducting an analysis of the bounds provided by their linear relaxations. By doing this, we show that it is possible to improve the tightness of the natural ILP formulation of the problem by adding specific constraints or modifying its structure with symmetry breaking approaches. Specifically, we adapt the Asymmetric Representative Formulation for the Vertex Coloring Problem (VCP) to our case, in order to mitigate the symmetry present in natural BPPS formulations.

The theoretical results are confirmed by our computational experiments, which show that the performances of the modified formulations are better than the ones of the standard alternative.

Our findings contribute to a deeper understanding of the BPPS landscape, its theoretical properties and practical implications.

Keywords

Status: accepted

Back to the list of papers