Optimizing a linear function over an efficient set

The problem (P) of optimizing a linear functiond ^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 directiond and the set of domination directionsD, ifd ^T 0 for all nonzero D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point , if there is no adjacent efficient edge yielding an increase ind ^T x, then a cutting plane is used to obtain a multiple-objective linear program ( ) with a reduced feasible set and an efficient set . To find a better efficient point, we solve the problem (I_i) of maximizingc _i ^T x over the reduced feasible set in ( ) sequentially fori. If there is a that is an optimal solution of (I_i) for somei and , then we can choosex ⁱ 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 is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.