Near-optimal solutions for the generalized max-controlled set problem

作者：Santos Ivairton M; Martinhon Carlos A^*; Ochi Luiz S

来源：Computers & Operations Research, 2010, 37(10): 1805-1813.

DOI：10.1016/j.cor.2010.01.012

• Sandwich graph problems
• Approximation algorithms
• Linear programming
• Heuristic
• Tabu search

In this work we deal with sandwich graphs G=(V,E) and present the notion of vertices f-controlled by a subset M subset of V. We introduce the generalized max-controlled set problem (GMCSP), where minimum gaps (defined by function f) and positive weights are associated to each vertex of V. In this case, the objective is to find a sandwich graph G in order to maximize the sum of the weights associated to all vertices f-controlled by M. We present a 1/2-approximation algorithm for the GMCSP and a new procedure for finding feasible solutions based on a linear relaxation. These solutions are then used as starting point in a local search procedure (Tabu Search with Path Relinking) looking for solutions of better quality. Finally, we present some computational results and compare our heuristics with the optimum solution value obtained for some instances of the problem.

• 出版日期2010-10