A mixed integer linear programming model and variable neighborhood search for Maximally Balanced Connected Partition Problem

This paper deals with Maximally Balanced Connected Partition (MBCP) problem. It introduces a mixed integer linear programming (MILP) formulation of the problem with polynomial number of variables and constraints. Also, a variable neighborhood search (VNS) technique for solving this problem is presented. The VNS implements the suitable neighborhoods based on changing the component for an increasing number of vertices. An efficient implementation of the local search procedure yields a relatively short running time. The numerical experiments are made on instances known in the literature. Based on the MILP model, tests are run using two MILP solvers, CPLEX and Gurobi. It is shown that both solvers succeed in finding optimal solutions for all smaller and most of medium scale instances. Proposed VNS reaches most of the optimal solutions. The algorithm is also successfully tested on large scale problem instances for which optimal solutions are not known.