A new relaxation for the set problems

Abstract

Set problems (SP) are an important class of combinatorial optimization problems which have many practical applications. Network relaxations of SP are alternative ways of relaxing the problem to find quick lower bound on the value of the objective function. Inspired by these relaxations, a new simple and much faster relaxation of the set problems is proposed. Using a standard cost allocation strategy and an innovative, the new relaxation is applied to a number of standard SP test problems and computational results are presented.