Comparing Solution Methods for the Quadratic Bin Packing Problem
H.A. de Mol van Otterloo (TU Delft - Electrical Engineering, Mathematics and Computer Science)
F.J.J. de Meijer – Mentor (TU Delft - Discrete Mathematics and Optimization)
W.G.M. Groenevelt – Graduation committee member (TU Delft - Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The Bin Packing Problem is a famous NP-hard problem in the field of optimization where items need to be packed in as few bins as possible. The problem has many applications across different fields. The Quadratic Bin Packing Problem (QBPP) is an extension of the Bin Packing Problem where a joint cost is added when two items are packed together and is NP-hard as well. The problem is quite unknown but has applications is for example hospital organisations or advertisement placement. In this thesis we relax the QBPP via linear programming and semidefinite programming and compare these relaxations by relative optimality gap and computation time. In particular the SDP relaxation has not been done before and has been found to generally work well in relaxing quadratic problems. We find that for low values of n the problem can best be solved as an integer quadratic program. For large values of n we find the SDP relaxation to be optimal giving tight bounds in a reasonable amount of time. Like similar research in this field, we also find SDP relaxations give a strong and fast bound to integer quadratic programs.