On the diversity of test instances for studying branch‐and‐bound performance

Abstract

Summary In their paper ‘An Automatic Method for Solving Discrete Programming Problems’, Ailsa Land and Alison Doig developed a branch‐and‐bound method for solving the general case of the mixed integer linear programming (MIP) problem. A core part of the algorithm, branch variable selection, has received renewed attention in recent years with the application of machine learning methods to train new selection rules. In this paper, we consider the sources of test instances used both to train these new methods and to assess their performance against existing methods. We apply instance space analysis (ISA) to assess the sufficiency of generated test cases for this purpose and show how test instance diversity can be intentionally increased to support new insights into the many factors influencing MIP solver performance. The paper presents a case study comparing pseudocost branching to full strong branching. We propose methods to ensure improved diversity of test instances in both feature and performance spaces and show that new instances that have been evolved to be more discriminating between different branching strategies are necessary to add sufficient diversity to support meaningful conclusions. While the case study is a small‐scale illustration of the need for diverse test instances, the proposed approach is generalisable to tackle future exploration of the many factors influencing MIP solver performance.