  We introduce the strongly NP-complete pagination problem, an extension of BIN
PACKING where packing together two items may make them occupy less volume than
the sum of their individual sizes. To achieve this property, an item is defined
as a finite set of symbols from a given alphabet: while, in BIN PACKING, any
two such sets would be disjoint, in PAGINATION, they can share zero, one or
more symbols. After formulating the problem as an integer linear program, we
try to approximate its solutions with several families of algorithms: from
straightforward adaptations of classical BIN PACKING heuristics, to dedicated
algorithms (greedy and non-greedy), to standard and grouping genetic
algorithms. All of them are studied first theoretically, then experimentally on
an extensive random test set. Based upon these data, we propose a predictive
measure of the statistical difficulty of a given instance, and finally
recommend which algorithm should be used in which case, depending on either
time constraints or quality requirements.
