Heuristic generation via parameter tuning for online bin packing
Online bin packing requires immediate decisions to be made for placing an incoming item one at a time into bins of fixed capacity without causing any overflow. The goal is to maximise the average bin fullness after placement of a long stream of items. A recent work describes an approach for solving...
| Main Authors: | , , , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
2014
|
| Online Access: | https://eprints.nottingham.ac.uk/34400/ |
| _version_ | 1848794844237922304 |
|---|---|
| author | Yarimcam, Ahmet Asta, Shahriar Özcan, Ender Parkes, Andrew J. |
| author_facet | Yarimcam, Ahmet Asta, Shahriar Özcan, Ender Parkes, Andrew J. |
| author_sort | Yarimcam, Ahmet |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Online bin packing requires immediate decisions to be made for placing an incoming item one at a time into bins of fixed capacity without causing any overflow. The goal is to maximise the average bin fullness after placement of a long stream of items. A recent work describes an approach for solving this problem based on a ‘policy matrix’ representation in which each decision option is independently given a value and the highest value option is selected. A policy matrix can also be viewed as a heuristic with many parameters and then the search for a good policy matrix can be treated as a parameter tuning process. In this study, we show that the Irace parameter tuning algorithm produces heuristics which outperform the standard human designed heuristics for various instances of the online bin packing problem. |
| first_indexed | 2025-11-14T19:22:39Z |
| format | Conference or Workshop Item |
| id | nottingham-34400 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:22:39Z |
| publishDate | 2014 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-344002020-05-04T16:58:51Z https://eprints.nottingham.ac.uk/34400/ Heuristic generation via parameter tuning for online bin packing Yarimcam, Ahmet Asta, Shahriar Özcan, Ender Parkes, Andrew J. Online bin packing requires immediate decisions to be made for placing an incoming item one at a time into bins of fixed capacity without causing any overflow. The goal is to maximise the average bin fullness after placement of a long stream of items. A recent work describes an approach for solving this problem based on a ‘policy matrix’ representation in which each decision option is independently given a value and the highest value option is selected. A policy matrix can also be viewed as a heuristic with many parameters and then the search for a good policy matrix can be treated as a parameter tuning process. In this study, we show that the Irace parameter tuning algorithm produces heuristics which outperform the standard human designed heuristics for various instances of the online bin packing problem. 2014-12-12 Conference or Workshop Item PeerReviewed Yarimcam, Ahmet, Asta, Shahriar, Özcan, Ender and Parkes, Andrew J. (2014) Heuristic generation via parameter tuning for online bin packing. In: 2014 IEEE Symposium on Evolving and Autonomous Learning Systems (EALS), 9-12 Dec 2014, Orlando, Florida. http://dx.doi.org/10.1109/EALS.2014.7009510 10.1109/EALS.2014.7009510 10.1109/EALS.2014.7009510 10.1109/EALS.2014.7009510 |
| spellingShingle | Yarimcam, Ahmet Asta, Shahriar Özcan, Ender Parkes, Andrew J. Heuristic generation via parameter tuning for online bin packing |
| title | Heuristic generation via parameter tuning for online bin packing |
| title_full | Heuristic generation via parameter tuning for online bin packing |
| title_fullStr | Heuristic generation via parameter tuning for online bin packing |
| title_full_unstemmed | Heuristic generation via parameter tuning for online bin packing |
| title_short | Heuristic generation via parameter tuning for online bin packing |
| title_sort | heuristic generation via parameter tuning for online bin packing |
| url | https://eprints.nottingham.ac.uk/34400/ https://eprints.nottingham.ac.uk/34400/ https://eprints.nottingham.ac.uk/34400/ |