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 characterized 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 formulations are typically large in size and therefore difficult to handle, 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 test calculations based on benchmark instances. Remarkably, the new cuts also lead to theoretical results about the optimal value of the LP relaxation.
Citation
Preprint MATH-NM-01-2022, Technische Universität Dresden