OPTIMIZING A LINEAR FUNCTION OVER AN EFFICIENT SET

The problem (P) of optimizing a linear function d(T)x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function direction d and the set of domination directions D, if d(T) pi greater than or equal to 0 for all nonzero pi epsilon D), then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point ($) over cap chi, if there is no adjacent efficient edge yielding an increase in d(T)x, then a cutting plane d(T)x = dT chi is used to obtain a multiple-objective linear program (($) over bar M) with a reduced feasible set and an efficient set ($) over bar E To find a better efficient point, we solve the problem (I-i) of maximizing c(i)(T) chi, over the reduced feasible set in (($) over bar M) sequentially for i. If there is a x(i) epsilon ($) over bar E that is an optimal solution of (I-i) for some i and d(T) chi(i) > dT ($) over cap chi, then we can choose chi(i) as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point ($) over cap chi is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.