Bin Packing in the ''real world'': extensions of classical bin packing for item-bin compatibility constraints and data-robust settings
Event Date: 27 June 2019
Speaker: Noam Goldberg, Bar-Ilan University
Time: 3pm
Room: Strathclyde Business School, Cathedral Wing, CW406b
Abstract: The classical bin packing problem is to pack items of given sizes into the minimum number of unit-capacity bins (or containers). We consider a multi-type bin packing problem motivated by different requirements of items that could be shipped in either standard or costlier refrigerated containers and items that must be shipped in refrigerated containers. We generalize our previous results in the online setting for two item sizes to general item sizes. Our results include a 1.781 lower bound and 1.930 upper bound on the absolute competitive ratio.
We next model the problem as a robust two-stage two-item type offline bin packing problem. In the first stage, bins of different types are acquired while the quantity of items of each type to arrive in the second stage is uncertain. In the second stage, the items are packed into bins. The bins that are secured in the first phase must allow for all of the items to be packed in the worst-case scenario. We develop closed-form solutions for the optimal solution and an algorithm for special cases of this problem with unit-size items. We also develop and experiment with iterative row-generating and row-and-column generation schemes for solving a more general version of this problem with arbitrary item-bin compatibility structures.
Finally, we consider item size uncertainty which surprisingly has remains largely unexplored in the robust optimization framework. We conclude with some approximation algorithm results for robust classical bin packing with uncertain item sizes under the budgeted and knapsack uncertainty models.
Bio: Noam Goldberg completed a PhD in operations research at Rutgers University in 2009. It followed an early non-academic career in software and systems engineering in telecommunications. In his PhD thesis he applied and developed new operations research (OR) and mathematical programming techniques for machine learning. In particular he was among the first to consider sparse data classification models and decision rules from an OR viewpoint. This work earned a first prize in a contest of the INFORMS NJ chapter in 2009. During 2009-2011 he worked on security models in game theory during a postdoctoral fellowship at the Technion and during 2011-2012 he worked as a postdoctoral appointee at Argonne National Laboratory on cyber-security models and optimization. In 2013 he spent time as a postdoctoral associate at Carnegie Mellon University working on optimization models for TV/video advertising. His postdoctoral fellowships were funded by multiple sources including VATAT, the Israeli Ministry of Absorption, the Daniel Rose Yale University - Technion initiative and NSF.
Noam joined Bar-Ilan University as a (tenure-track) lecturer in 2013 and was promoted to a senior lecturer with tenure effective in 2018. He is an active member of the data science institute at Bar-Ilan and several professional associations including ORSIS, EURO and MOS. He has more than 20 peer reviewed publications including top journals in optimization and operations research and conference proceedings in computer science. In his current work he continues to be motivated by high-impact societal applications for data driven optimization models, game models and solution techniques.
Published: 13 June 2019
