Sparse, continuous policy representations for uniform online bin packing via regression of interpolants
View/ Open
Volume
10197 LNCS
Pagination
189 - 200
ISBN-13
9783319554525
DOI
10.1007/978-3-319-55453-2_13
ISSN
0302-9743
Metadata
Show full item recordAbstract
© Springer International Publishing AG 2017. Online bin packing is a classic optimisation problem, widely tackled by heuristic methods. In addition to human-designed heuristic packing policies (e.g. firstor bestfit), there has been interest over the last decade in the automatic generation of policies. One of the main limitations of some previously-used policy representations is the trade-off between locality and granularity in the associated search space. In this article, we adopt an interpolation-based representation which has the jointly-desirable properties of being sparse and continuous (i.e. exhibits good genotype-to-phenotype locality). In contrast to previous approaches, the policy space is searchable via real-valued optimization methods. Packing policies using five different interpolation methods are comprehensively compared against a range of existing methods from the literature, and it is determined that the proposed method scales to larger instances than those in the literature.