A steepest edge rule for a column generation approach to the convex re-coloring problem

Abstract

The convex recoloring problem is a clustering problem to partition nodes of a network into connected subnetworks. We develop a hybrid rule combining the Dantzig's Rule and the Steepest Edge Rule to produce columns which enter into the basis of the master problem in the column generation framework introduced by Chopra et al. (Modeling and Optimization: Theory and Applications (MOPTA 2016), pp 39-53, 2017). The hybrid rule leads to only a small number of iterations and makes it possible to perform the column generation approach in an undergraduate class using Microsoft Excel. We perform a large scale computational experiment and show that the hybrid rule is effective.