Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Aufsatznummer | e283503 |
Seitenumfang | 26 |
Fachzeitschrift | Pesquisa Operacional |
Jahrgang | 44 |
Publikationsstatus | Veröffentlicht - 2024 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85202526667 |
---|---|
ORCID | /0000-0003-0953-3367/work/168719961 |