Lower bounds and heuristic algorithms for the $k_i$-partitioning problem