Optimizing over the efficient set using a top–down search of faces

The problem of optimizing a linear function over the efficient set of a multiple objective linear programming problem is studied. The decomposition of the efficient set into efficient faces is used as the basis of a search-based algorithm to solve this problem. The faces of the feasible region are characterized by the set of constraints that hold as equality in that face. The search is conducted over the indices of the constraints in a way that explores faces of possibly higher dimension first. Computational tests are performed to establish the behavior of the algorithm when the objective function is built according to different schemes that have received attention in the literature. The results indicate that different objective function types may lead to varying computation time requirements. In general, computational requirements of the algorithm increase significantly with problem size. A heuristic modification of the algorithm is proposed to solve large problems within reasonable time limits. Tests to measure the quality of the heuristic solutions show that the heuristic approach constitutes a practical alternative for finding good solutions for the problem.