Tolerances for weights in multiobjective linear programming

This thesis deals with the computation of the maximal tolerance of weight in scalariza- tion problems of multiobjective linear programming. The maximal tolerance is defined as the largest feasible perturbation of scalarization weights for which a given solution remains efficient. Attention is paid to methods based on a conic characterization of optimality using the tangent cone and its extreme directions. For the case of a fixed scalarization, a formula for computing the maximal tolerance is presented. Furthermore, a method for selecting a scalarization that maximizes the maximal tolerance is proposed. The proposed methods are compared with known approaches based on basis stability in terms of solution quality, computational complexity, and classes of problems to which the methods can be applied. It is proved that the general problem of finding the maximal tolerance is co-NP-complete.