Jorge Ivan Serna

• The goal of a multicriteria program is to explore different possibilities and their respective compromises which adequately represent the nondominated set. An exact description will in most cases fail because the number of efficient solutions is either too large or even infinite. We approximate the nondominated by computing a finite collection of nondominated points. Different ideas have been applied, including nonnegative weighted scalarization, Tchebycheff weighted scalarization, block norms and epsilon-constraints. Block norms are the building blocks for the inner and outer approximation algorithms proposed by Klamroth. We review these algorithms and propose three different variants. However, block norm based algorithms require to solve a sequence of subproblems, the number of subproblems becomes relatively high for six criteria and even intractable for real applications with nine criteria. Thus, we use bilevel linear programming to derive an approximation algorithm. We finally analyze and compare the approximation quality, running time and numerical convergence of the proposed methods.