Multiple objective programming with piecewise linear functions

An approach to generating all efficient solutions for multiple objective programs with piecewise linear objective functions and linear constraints is presented. The approach is based on the decomposition of the feasible set into subsets, referred to as cells, so that the original problem reduces to a series of single objective linear programs and feasibility tests over the cells. The concepts of cell-efficiency and complex-efficiency are introduced and their relationship with efficiency is examined. A generic algorithm for finding efficient solutions for bi-objective piecewise linear programs is proposed. Applications in location theory as well as in worst case analysis are highlighted.