ALGO Talk - A Weight Set Decomposition Method for the Weighted Tchebycheff Scalarization

Talk by Stephan Helfrich, Optimization Group, Technical University of Kaiserslautern, 27 Oct 2020

Abstract:

In general, solving the weighted Tchebycheff scalarization problem is an adequate way to calculate supported as well as unsupported nondominated images of discrete multiobjective optimization problems. For a nondominated image y, the associated weight set component is defined by all weights under which y is optimal for the corresponding weighted Tchebycheff scalarization problem. Hence, the weight set can be decomposed into subsets whose structures allow a design of efficient solution methods and the study of ”robustness of images under preferences”. Weight set decomposition under the weighted sum scalarization has extensively been studied, although unsupported images cannot be calculated. We present the weight set decomposition for the weighted Tchebycheff scalarization, provide fundamental geometric properties of the weight set components and propose an adaption of the algorithm developed in [1, 2] to calculate the full decomposition including all nondominated images. Further, we introduce a Tchebycheff variant of the partial Dichotomic search algorithm, and show, restricting to tri-objective discrete optimization problem, how it can be utilized to iteratively enlarge weight set components.

[1] K. Dächert, K. Klamroth, R. Lacour, and D. Vanderpooten. Efficient computation of the search region in multi-objective optimization. European Journal of Operational Research, 260(3):841 – 855, 2017.

[2] Kathrin Klamroth, Renaud Lacour, and Daniel Vanderpooten. On the representation of the search region in multi-objective optimization. European Journal of Operational Research, 245(3):767 – 778, 2015.