Multiple Objective Linear Programming with Parametric Criteria Coefficients

In this paper we study the multiple objective linear programming problem with parametric criteria coefficients. This problem is of interest since in many situations the coefficients of the objective functions of a multiple objective linear program either represent estimates of the true data or are subject to systematic variations. Properties of this problem are developed, and an algorithm for generating the set of all weakly-efficient extreme points of this problem is described. To implement this algorithm, a nonconvex subproblem must be solved for each candidate extreme point encountered. This is accomplished by applying the Generalized Benders Decomposition method. Computational results concerning the solution of these subproblems are presented.