This repository includes source code written in C and MATLAB for extracting features from a given set of instances for the Maximum Flow Problem (MFP). It also facilitates the selection of unbiased instances based on their feature values. The chosen instances are then employed in the Instance Space Analysis (ISA) to discern the impact of features on the performance of MFP algorithms. To implement ISA, the toolkit provided by MATILDA is utilised, which is available at https://github.com/andremun/InstanceSpace. The generated instance space can be explored online at see MATILDA - MFP Instance Space Analysis.
- Benchmarks used here are in DIMACS format (see http://archive.dimacs.rutgers.edu/pub/netflow/generators/network/).
dimacs_baisc_factors_sorted.c is a C source code designed to extract the basic factors of a given network in DIMACS format. These basic factors include numNodes, numArcs, NetCap, maxcap, mincap, SrcAAC, SnkAAC, Src_degree, Snk_degree, AvCap, StDAC, NmBdCap, NmGdCap, PotNetExcess, PotNetDeficit, StDAvNdDg, and various other features found in the code. The extracted basic factors are then utilized by ISAFtrExtractorPool_InitilizeTime_mod_pool.m to extract the final features employed in the instance space analysis for MFP (see MATILDA - MFP Instance Space Analysis).
ISA.m is the main script controlling different functions, including "ISAFtrExtractorPool_InitilizeTime_mod_pool," to generate the metadata used in the instance space analysis.
purifyInst.m is the source for the instance selection algorithm, which takes the metadata generated by ISA and filters instances based on their similarity and the similarity of the algorithm's performances on them. CVNND.m calculates the number of instances, uniformity, and ViSA ratio for the critical set of instances returned by purifyInst.m.
CSV files serve as the metadata for MFP; Metadata_M0.csv represents the initial metadata, while Metadata_M0'.csv is the augmented metadata obtained by adding new instances to Metadata_M0.csv. Subsequently, Metadata_M2.csv results from applying the instance selection process to Metadata_M0'.csv. For more details on obtaining Metadata_M0'.csv and Metadata_M2.csv, we refer readers to the following paper.
Enhanced Instance Space Analysis for the Maximum Flow Problem
by: Hossein Alipour, Mario Andrés Muñoz, Kate Smith-Miles
European Journal of Operational Research
2022
https://doi.org/10.1016/j.ejor.2022.04.012
Code by: Hossein Alipour
School of Mathematics and Statistics
The University of Melbourne
Australia
2021
Email: halipour@alumni.unimelb.edu.au
Copyright: Hossein Alipour
