Path Relinking Scheme for the Max-Cut Problem

Background

Path relinking method searches for solutions of an optimization problem along the trajectories that connect solutions from a given set (Glover, Laguna & Marti, 2000). The most common path relinking scheme involves a pair of solutions: an initiating solution and a guiding solution. A set of moves (transformations) are applied starting in the initiating solution that sequentially introduce the attributes of the guiding solution. Usually, such moves result in a sequence of solutions that lie on a path between the initial solution pair.

Assuming that the weights of the graph edges are non-negative, the maximum cut problem can be formulated by the following mixed-integer program (Kahruman, Kolotoglu, Butenko & Hicks, 2007):

The optimal solution vector x defines a graph partition (if then , otherwise ) that has the maximum cut value, the sum of weight of edges connecting different partititions. Let denote a cost of a cut corresponding to the solution vector x.