×

An integer linear programming formulation and genetic algorithm for the maximum set splitting problem. (English) Zbl 1289.90142

The authors first introduce an integer linear programming formulation for the maximum set splitting problem, with the proof of its correctness. Additionally, an evolutionary metaheuristic is proposed for solving proposed problem in order to solve large-scale instances. It is used the binary representation, mutation with frozen genes, limited number of different individuals with the same objective value and the caching technique. Numerical results, on the two data sets proposed from the literature, show that both CPLEX solver, based on this ILP formulation, and the genetic algorithm, produce very good solutions.

MSC:

90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI