Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.