A group theoretic approach to metaheuristic local search for partitioning problems

Recent work has demonstrated the power of combining group theory with metaheuristic search methodologies to solve discrete optimization problems. Group theory provides tools to characterize the underlying structures in move neighborhoods, solution representations and solution landscapes. Exploiting these structures with group theoretic techniques produces highly effective and efficient search algorithms. Using group theory we develop a methodology for partitioning the solution space into orbits. The partitioning is performed by clustering the variables based on the reduced costs of the LP relaxation creating “good” and “bad” orbits. We are able to calculate the size of each orbit and place upper and lower bounds on the solutions contained within. The search efforts can then be directed on the “good” orbits. Based on these ideas, we develop a Group Theoretic Tabu Search (GTTS) algorithm for solving the unicost Set Covering Problem (SCP), GTTS-USCP. We tested our algorithm on 65 benchmark problems and compared the results against the previous best known and solutions obtained by CPLEX 9.0. GTTS-USCP discovered 46 new best known solutions. GTTS-USCP converged significantly faster than CPLEX for all problem sets. We explore the general integer linear program (ILP) by way to the group minimization problem (GMP). By examining the local search in terms of the GMP, we gain insights that will help us solve the ILP. We describe the local search for the corner polyhedron in the space of the non-basic variables. Integer points in the corner polyhedron that produce an all integer basis form a sub-lattice. We develop identity move neighborhoods that allow the local search to traverse this sub-lattice. We also develop bound strengthening of the non-basic variables based on reduced costs. These bounds effectively shrink the corner polyhedra reducing the size of the solution space we must search. Based on this research, we develop a GTTS algorithm for solving the GMP, GTTS-GMP. Since the GMP can be formed from any ILP, this algorithm solves the general ILP. The algorithm performs well on a diverse set of benchmark problems.