AN INTERIOR MULTIPLE-OBJECTIVE PRIMAL-DUAL LINEAR-PROGRAMMING ALGORITHM USING EFFICIENT ANCHORING POINTS

We present an interior Multiple Objective Linear Programming (MOLP) al gorithm based on the path-following primal-dual algorithm. In contrast to the simplex algorithm, which generates a solution path on the exte rior of the constraints polytope by following its vertices, the path-f ollowing primal-dual algorithm moves through the interior of the polyt ope. Interior algorithms lend themselves to modifications capable of a ddressing MOLP problems in a way that is quite different from current solution approaches. In addition, moving through the interior of the p olytope results in a solution approach that is less sensitive to probl em size than simplex-based MOLP algorithms. The modification of the in terior single-objective algorithm to MOLP problems, as presented here, is accomplished by combining the step direction vectors generated by applying the single-objective algorithm to each of the cost vectors in to a combined direction vector along which we step from the current it erate to the next iterate.