The branch-and-bound algorithm is used by solvers to efficiently find the optimal solution of discrete optimisation problems. It does so by sequentially partitioning parts of the search space based on the solution to the linear relaxation of the problem. This sequential decision-making is performed by the variable selection and node selection heuristics. The sequential nature of these heuristics makes them suitable for trajectory-based learning in the form of imitation learning and reinforcement learning. Learning problem-specific heuristics in this way has become increasingly popular in recent years. Despite their similarities, the two heuristics have very different dynamics during learning, and success has mainly been achieved for variable selection. In this work, we evaluate the node selection problem and formulate a learning to select paradigm for both imitation and reinforcement learning. We find that learning to select is generally more difficult due to the small margin of possible improvement over the current baselines, and the lack of informative features to distinguish nodes during ranking. These challenges are exacerbated by focusing on sibling comparisons, which are generally the most difficult due to the high similarity between the nodes. Sibling comparisons are also arguably the most important in node selection, however, due to the importance of plunging to reduce context switching overhead. The results indicate that both approaches fail to learn meaningful decision-making policies based on the limited fixed-size feature representation of the nodes. A code repository for reproducing and extending the experiments is publicly available at https://github.com/jgroenheide/rl2select.

Multi-Level variants of classic optimisation problems are becoming more noteworthy as the complexity of real life applications increases. In this research we investigate the Multi-Level Bin Packing optimisation problem, which models, for example, global logistics and part manufacturing. We will look at the performance of solving Integer Linear Programming formulations of the Multi-Level Bin Packing problem using IBM ILOG CPLEX Optimization Studio, and compare these results to the performance of simple heuristic-based algorithms to reach conclusions about the usefulness of optimal-solution algorithms for NP-Hard problems. We ultimately find that the simple heuristics leave a large gap in optimality, while the solving time for finding optimal solutions is still too large for practical instances. As such, we conclude that more specialised algorithms are needed that can balance the time cost and optimality, depending on the application.