An algorithm based on Branch-and-Bound method for finding all non-dominated points of MOCO problem

Abstract

In this paper we introduce a novel algorithm for finding all non-dominated points of MOCO problems. Likewise a branch and bound method, our algorithm splits the feasible set in certain smaller sub-sets, and then performs the optimization of an aggregation of the original objective functions over each sub-set. However, the defined sub-sets are non-disjunctive, and in order to reduce the computational complexity, our implementation memorizes two lists of bounds: one containing those bounds that were found infeasible, and another containing the bounds that were successfully used in previous optimization steps. We report our numerical results obtained by solving multiple objective knapsack problems from a benchmark found in the literature.