(340a) Augmented Epsilon Constraint Method for the Multi-Objective Optimization of Combinatorial Optimization Problems

A major challenge in multi-objective combinatorial optimization is to develop effective algoritjms to generate efficient solutions. It is known that, the number of efficient solutions increase exponentially with respect to the problem size in general. In this work, a new variant of the epsilon constraint method for solving combinatorial multi-objective optimization problems is developed. A penalty parameter is added to the objective function of the subproblems is added. We drive the bounds on the penalty parameter that is a function of system parameters and show that below a threshold value the epsilon constraint algorithm may miss some of the efficient solutions. The proposed algorithm is tested on various benchmark problems including assignment, knapsack and set covering. Analysis of the results indicate that the proposed algorithm is able to obtain the entire efficient set for the benchmark problems more effectively.