Bin packing with linear usage costs - An application to energy management in data centres

EnergeTIC is a recent industrial research project carried out in Grenoble on optimizing energy consumption in data-centres. The efficient management of a data-centre involves minimizing energy costs while ensuring service quality. We study the problem formulation proposed by EnergeTIC. First, we focus on a key sub-problem: a bin packing problem with linear costs associated with the use of bins. We study lower bounds based on Linear Programming and extend the bin packing global constraint with cost information. Second, we present a column generation model for computing the lower bound on the original energy management problem where the pricing problem is essentially a cost-aware bin packing with side constraints. Third, we show that the industrial benchmark provided so far can be solved to near optimality using a large neighborhood search.