Advancing local search approximations for multiobjective combinatorial optimization problems

This study proposes a theoretical framework for defining approximations of the Pareto sets of multiobjective combinatorial optimization (MOCO) problems. The concept of t-representation is proposed for modeling the approximation quality and describes a local search algorithm to produce a t-representation. Unlike the current local search algorithms found in the literature, the proposed algorithm yields a representation for the Pareto set with a mathematically proven error term (quality). The algorithm starts with an initial representation containing efficient solutions. The approximation quality is derived mathematically and is measured using a tolerance function that depends on the cost coefficients of the problem and the initial representation. The computational experiments are conducted using two types of MOCO problems (multiobjective set covering problem and multiobjective knapsack problem). The computational results demonstrate that this algorithm significantly outperforms the initial representation, obeys the theoretical bounds, and efficiently solves MOCO problems.