Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

The temporal bin packing problem with fire-ups (TBPP-FU) is a two-dimensional packing problem where one geometric dimension is replaced by a time horizon. The given items (jobs) are char-acterized by a resource consumption, that occurs exclusively during an activity interval, and they have to be placed on servers so that the capacity constraint is respected at any time. For energy efficiency reasons, an optimal assignment shall minimize a weighted sum of the number of servers in use and the number of switch-on processes (so-called fire-ups) resulting from the selected configuration. The associated ILP for-mulations are typically large in size, so that, in the recent past, several model improvements have already been proposed in the literature. However, with only one exception, all these techniques do not address the quality of the LP bound which is another crucial factor for the size of the branch-and-bound trees generated during the solution process. To this end, we present a new class of valid inequalities, contributing to a stronger LP relaxation, and discuss their numerical benefits by computational experiments based on benchmark instances and new test sets. Remarkably, the new cuts also lead to theoretical results about the optimal value of the LP relaxation.

Details

Original languageEnglish
Article numbere283503
Number of pages26
JournalPesquisa Operacional
Volume44
Publication statusPublished - 2024
Peer-reviewedYes

External IDs

Scopus 85202526667
ORCID /0000-0003-0953-3367/work/168719961

Keywords

Sustainable Development Goals