This thesis considers a Graph Disconnection Problem(GDP), which is to find a set of edges and nodes such that the total cost of removing the edges is no more than a given budget while maximizing the total weight of nodes disconnected from a given source node.
We propose two new models, which have polynomial number of constraints and variables compared to the previous model that has exponential number of constraints.
Since this problem is NP-hard, we propose a meta-heuristic algorithm. This algorithm consists of two stages; preprocessing stage and tabu search stage. The preprocessing stage reduces the problem size. We examined infeasible solutions as well as feasible solutions in the tabu search.
We tested the algorithm on 360 instances which were randomly generated and obtained optimal solutions except for 20 instances.
