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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummere283503
Seitenumfang26
FachzeitschriftPesquisa Operacional
Jahrgang44
PublikationsstatusVeröffentlicht - 2024
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Ziele für nachhaltige Entwicklung