An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems

The augmented weighted Tchebycheff norm was introduced in the context of multicriteria optimization by Steuer and Choo [21] in order to avoid the generation of weakly nondominated points. It augments a weighted l(infinity)-norm with an l(1)-term, multiplied by a "small" parameter rho > 0. However, the appropriate selection of the parameter rho remained an open question: A too small value of rho may cause numerical difficulties, while a too large value of rho may lead to the oversight of some nondominated points. For discrete bicriteria optimization problems we derive a method for a problem dependent determination of all parameters of the augmented weighted Tchebycheff norm such that all nondominated points can be found and rho is as large as possible. In a computational study based on randomly generated instances of a bicriteria knapsack problem, the resulting adaptive augmented weighted Tchebycheff method is compared with the lexicographic weighted Tchebycheff method and with the augmented weighted Tchebycheff method with preset parameter values as well as with augmented a-constraint scalarizations. (C) 2012 Elsevier Ltd. All rights reserved.