A MILP model for the connected multidimensional maximum bisection problem

The Maximum Bisection Problem (MBP) is a well-known combinatorial optimization problem that has been proven to be NP-hard. The maximum bisection of a graph is the partition of its set of vertices into two subsets with an equal number of vertices, where the weight of the edge cut is maximal. This work introduces a connected multidimensional generalization of the Maximum Bisection Problem. In this NP-hard problem, weights on edges are vectors of non-negative numbers, and subgraphs induced by partitions must be connected. A mixed integer linear programming (MILP) formulation is proposed with proof of its correctness. The MILP formulation of the problem has a polynomial number of variables and constraints