The bin packing problem with item class setups
Dr. Stefano Coniglio
University of Southampton, UK
DEIB - Seminar Room (building 20)
April 17th, 2019
2.15 pm
Contacts:
Edoardo Amaldi
Research Line:
Operations research and discrete optimization
University of Southampton, UK
DEIB - Seminar Room (building 20)
April 17th, 2019
2.15 pm
Contacts:
Edoardo Amaldi
Research Line:
Operations research and discrete optimization
Abstract
We introduce and investigate the Bin Packing Problem with Setups (BPPS), a generalization of the bin packing problem in which the items are partitioned into classes, each having a setup weight and a setup cost. We first investigate a natural formulation of the problem with a variable for each pair of item and bin, and show how its linear programming relaxation can be solved in closed-form in linear time and establish an asymptotic bound on its optimality gap. We then propose an approximation scheme for combining approximation algorithms for the classical bin packing problem so to obtain solutions to the BPPS within a constant approximation factor. We then propose a formulation with exponentially-many columns suitable for column generation methods, and propose a branch-and-cut-and-price algorithm based on it. The method relies on a two-level branching scheme and on the separation of subset row inequalities, and it is also enhanced via a preprocessing procedure and a bound-tightening one. Extensive computational experiments show the effectiveness of our approach when compared to off-the-shelf methods.
This is joint work with Fabio Furini.
This is joint work with Fabio Furini.
Short Bio
Dr. Stefano Coniglio is a Lecturer (Assistant Professor) in Operations Research within Mathematical Sciences at the University of Southampton, UK. Prior to joining the University of Southampton in February 2016, he served as Research Associate at the RWTH Aachen University, Germany, and as Postdoctoral Researcher at Politecnico di Milano, Italy (where he received his PhD in Information Technology in 2011). His research focuses on exact methods for the solution of mathematical programming problems with combinatorial/integer aspects. Recently, he has been active in bilevel programming, robust optimization, and methodological aspects of cutting plane generation, with applications ranging from algorithmic game theory to optimization in telecommunication networks, energy production planning and energy markets, and machine learning.