Implicit Enumeration for Representation Systems in Multi-objective Optimization

Abstract

The main focus of this thesis is the design and analysis of algorithms to nd a representative subset, with a given cardinality, of the Pareto-optimal set for the unconstrained bi-objective knapsack problem, according to some notions of representation quality. The representative subset should be obtained without prior knowledge of the Pareto-optimal set. Two main algorithms are discussed in this thesis. The rst reformulates the recurrence of the existing Nemhauser-Ullman algorithm for the unconstrained bi-objective knapsack problem by selecting a representative subset at each recursive step. The second by pruning solutions that may not contribute to nd the optimal representation based on the sum of the weights or the set of supported solutions. Analysis on the time and error regarding the uniformity, coverage and -indicator is performed. Keywords: Unconstrained bi-objective knapsack problem, Nemhauser-Ullman algorithm, Representative subset, Representation quality