Stress testing mixed integer programming solvers through new test instance generation methods Article Swipe

Optimisation algorithms require careful tuning and analysis to perform well in practice. Their performance is strongly affected by algorithm parameter choices, software, and hardware and must be analysed empirically. To conduct such analysis, researchers and developers require high-quality libraries of test instances. Improving the diversity of these test sets is essential to driving the development of well-tested algorithms. This thesis is focused on producing synthetic test sets for Mixed Integer Programming (MIP) solvers. Synthetic data should be carefully designed to be unbiased, diverse with respect to measurable features of instances, have tunable properties to replicate real-world problems, and challenge the vast array of algorithms available. This thesis outlines a framework, methods and algorithms developed to ensure these requirements can be met with synthetically generated data for a given problem. Over many years of development, MIP solvers have become increasingly complex. Their overall performance depends on the interactions of many different components. To cope with this complexity, we propose several extensions over existing approaches to generating optimisation test cases. First, we develop alternative encodings for problem instances which restrict consideration to relevant instances. This approach provides more control over instance features and reduces the computational effort required when we have to resort to search-based generation approaches. Second, we consider more detailed performance metrics for MIP solvers in order to produce test cases which are not only challenging but from which useful insights can be gained. This work makes several key contributions: 1. Performance metrics are identified which are relevant to component algorithms in MIP solvers. This helps to define a more comprehensive performance metric space which looks beyond benchmarking statistics such as CPU time required to solve a problem. Using these more detailed performance metrics we aim to produce explainable and insightful predictions of algorithm performance in terms of instance features. 2. A framework is developed for encoding problem instances to support the design of new instance generators. The concepts of completeness and correctness defined in this framework guide the design process and ensure all problem instances of potential interest are captured in the scheme. Instance encodings can be generalised to develop search algorithms in problem space with the same guarantees as the generator. 3. Using this framework new generators are defined for LP and MIP instances which control feasibility and boundedness of the LP relaxation, and integer feasibility of the resulting MIP. Key features of the LP relaxation solution, which are directly controlled by the generator, are shown to affect problem difficulty in our analysis of the results. The encodings used to control these properties are extended into problem space search operators to generate further instances which discriminate between solver configurations. This work represents the early stages of an iterative methodology required to generate diverse test sets which continue to challenge the state of the art. The framework, algorithms and codes developed in this thesis are intended to support continuing development in this area.