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 $$\hat x$$ , if there is no adjacent efficient edge yielding an increase ind T x, then a cutting plane $$d^T x = d^T \hat x$$ is used to obtain a multiple-objective linear program ( $$\bar M$$ ) with a reduced feasible set and an efficient set $$\bar E$$ . To find a better efficient point, we solve the problem (Ii) of maximizingc x over the reduced feasible set in ( $$\bar M$$ ) sequentially fori. If there is a $$x^i \in \bar E$$ that is an optimal solution of (Ii) for somei and $$d^T x^i > d^T \hat x$$ , then we can choosex 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 $$\hat x$$ is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.