Pattern based learning and optimisation for online packing problems

Abstract

Patterns and their identification are essential tasks in data mining applications. However, few studies have systematically investigated the dynamics of pattern values or their reuse under varying conditions. When problem conditions change, previously effective patterns may become less effective, leading to suboptimal solutions. Therefore, pattern-based optimisation algorithms must not only identify good quality patterns but also adapt to dynamic environments or imperfect predictions, through dynamic pattern valuations and adaptive learning for their combinations.

This thesis focuses on pattern-based approaches for solving online combinatorial optimisation problems. Although high-quality patterns can guide the generation of high-quality online solutions, existing research indicates that even minor errors can lead to a decline in the quality of the guided online solution, especially when dealing with dynamic problems. Accordingly, this thesis proposes a two-stage framework, Plan-and-Pack, for online \acrshort{cop}, which consists of learning and predicting future distributions during the planning phase to generate high-quality patterns, as well as adaptive decision-making based on observations and online learning during the online decision phase.

This thesis propose a novel scheme that connects data mining and duality theory in operations research for the efficient identification of patterns and dynamic quantification of their values. This method evaluates patterns based on their ability to meet stochastic constraints and their impact on the objective value. Additionally, this thesis address the updating of patterns to fit new realities through an online adjustment stage, where risky patterns are identified and replaced before packing.

This thesis primarily focuses on packing problems, including the classical one-dimensional online bin packing problem and the more practically relevant operating room scheduling problem. The methods proposed in this thesis have achieved state-of-the-art performance in terms of objective value in both cases. Furthermore, an in-depth analysis of the contributions to performance is also provided.

Date of Award	13 Jul 2025
Original language	English
Awarding Institution	University of Nottingham
Supervisor	Ruibin Bai (Supervisor), Jiawei Li (Supervisor) & Tieyan Liu (Supervisor)