Genetic programming policies for bin packing in the framework of deterministic Markov decision process

Abstract The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study focuses on minimizing waste and maximum lateness in a one-dimensional version of the BPP, which is particularly relevant in industrial contexts. The goal is to develop a constructive heuristic algorithm that can be adapted to various situations. We model the BPP as a Deterministic Markov Decision Process with discrete state and action spaces, where policies are represented by arithmetic expressions involving state variables. This approach allows for a clearer explanation of the decision process, in contrast to other methods like neural networks. To evolve these policies, we use Genetic Programming (GP). Trained on a set of BPP instances, the resulting policies are effective for solving new, unseen instances. In the experimental study, we explore different GP settings, including varying sets of symbols. The results reveal valuable insights about the importance of state variables, indicating that a smaller selection of them may yield the best results. The evolved policies are compared with an exact method from the literature, achieving similar outcomes but with significantly less computational time.