School of Mathematics and Statistics - Theses
Permanent URI for this collection
Search Results
1 - 1 of 1
-
ItemInstance Space Analysis for the Maximum Flow Problem( 2023)The Maximum Flow Problem (MFP) is a fundamental network flow theory problem, for which many algorithms, supported by strong theoretical worst-case analyses, have been proposed. Due to its theoretical and practical importance in network theory, designing effective algorithms for the Maximum Flow Problem (MFP) remains a focus of research efforts. Although the worst-case performance analysis is the main tool for examining the performance of these algorithms, their practical efficiency depends on the network structure, making it unclear which algorithm is best for a particular instance or a class of MFP. Instance Space Analysis (ISA) is a methodology that provides insights into the such per-instance analysis. In this thesis, the instance space of MFP is constructed and analysed for the first time. To this end, novel features from the networks are extracted, capturing the performance of MFP algorithms. Additionally, this thesis expands the ISA methodology by addressing the issue of how benchmark instances should be selected to reduce bias in the analysis. Using the enhanced ISA (EISA) methodology with MFP as the case study, this thesis demonstrates that the most important features can be detected, and machine learning methods can identify their impact on algorithm performance, whilst reducing the bias caused by over-representation within the selected sample of test instances. The enhanced methodology enables new insights into the performance of state-of-the-art general-purpose MFP algorithms, as well as recommendations for the construction of comprehensive and unbiased benchmark test suites for MFP algorithm testing. To get further insight into the strengths and weaknesses of the algorithms, CPU time and fundamental operations counts are used as algorithm performance measures. Using EISA, it is revealed that the arc/path finding strategies employed by the algorithms explain critical differences in the algorithms’ behaviours. We leverage these insights to propose two new initialisation strategies, which are an essential part of the arc/path finding strategy. To employ these new strategies on our previously studied algorithms, we propose modifications that result in 15 new algorithmic variants. We examine the impact of these proposed initialisation strategies on the algorithm performance and discuss the conditions under which each initialisation strategy is expected to improve the performance. The implementations of the new algorithmic variants are also presented. Finally, the limitations of the study and opportunities for interesting future work are discussed.