Dec 9 2022 11:00 am
A better Constraint Generation Algorithm and harder instances for the Minimum Connectivity Inference problem
Dr. Muhammad Abid Dar
Lab 9-1C1, First Floor, SSE building
This talk aims at describing two aspects, to tackle the well known Minimum Connectivity Inference (MCI) problem, which is an N Phard problem. The first idea focuses state of the art Constraint Generation Algorithm (CGA). In general, the CGA uses cutset formulation of the MCI problem in its successive iterations. However, the strength of multicut approach has been established in the literature. Therefore, the aspect of using multicut setup in iterative process of the CGA will be discussed. Secondly, the harder instances of the MCI problem will be reviewed. The factors effecting the hardness of such instances will be considered as well.
Dr. Dar did his PhD from Technische Universität, Dresden (Germany). During PhD, he worked on various methods to optimally solve an NP-hard problem of discrete optimization, known as the Minimum Connectivity Inference (MCI) problem. This problem has appeared in different scientific fields of applied nature like structural biology, engineering and computer science. His past work also consists of the simulation-based tests in which different mathematical models are solved by using solvers like CPLEX®