Speaker: Dr Sergey Polyakovskiy

Title: A feasibility constraints-guided matheuristic for a class of two-dimensional bin packing problems.

Abstract:

In this talk, we address a class of two-dimensional bin packing problems that pack a set of rectangular items into large rectangular bins to minimize the waste of the used bins. We focus on how these problems can be approximately solved via a sequence of low-level mixed-integer programs that reserve space for unpacked items and how such programs can be guided by feasibility constraints based on dual feasible functions. The embedded constraints constitute an efficient lookahead mechanism that prohibits the investigation of infeasible directions and constrains the search to improving ones. They forbid partial (feasible) solutions that would lead to infeasible solutions in future cycles; thus, they enable current decisions to account for their impact on future ones.

As an illustrative example, we consider the unweighed variable-sized two-dimensional bin packing problem where bins have different sizes and items must be obtained via guillotine cuts. We propose a matheuristic and discuss its search strategies, high-level diversification and intensification mechanisms that along with the application of the feasibility constraints make it an effective solution approach. For the variable-sized bin packing benchmark instances, the matheuristic matches and improves 90.8% of the primal bounds. For the single bin-size bin packing benchmark instances, the matheuristic further proves the optimality of 82.6% primal bounds.

Bio:

Dr Sergey Polyakovskiy is a Lecturer in Computer Science at the School of IT at Deakin University with both academic and industrial background. His research interests include mathematical and constrained programming, hybrid and decomposition optimization techniques, industrial applications, and optimization problems with multiple components.

WED 08 DEC AUGUST 4PM – 5PM AEST

ZOOM Meeting ID: 873 1557 5255; Password: 778635