Home Events AI-based Optimisation Seminar Series 2 Feb 2022


Feb 02 2022


4:00 pm - 5:00 pm



AI-based Optimisation Seminar Series 2 Feb 2022

Speaker: Dr Sergey Polyakovskiy

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


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.


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.


ZOOM Meeting ID: 873 1557 5255; Password: 778635

More Info

Zoom Link

The event is finished.


Feb 02 2022

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080

University of Melbourne
Parkville, Victoria, 3010

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)