/ISA_MFP

Instance space analysis for the maximum flow problem

Primary LanguageC

ISA_MFP

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.

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

DOI