A heuristic for estimating nadir criterion values in multiple objective linear programming

In this paper we further investigate the problem of finding nadir criterion values (minimum criterion values over the nondominated set) in multiple objective linear programming. Although easy to obtain, the minimum values present in a payoff table are unreliable and should only be used with caution, especially in problems that have more than a small number of extreme points. To obtain better estimates of the nadir criterion values without adding great complexity to the task, we present an approach based upon the use of reference directions. At each iteration of this approach, a reference direction is chosen that maximally minimizes the objective under consideration. We proceed with reference directions that accomplish this until the objective under consideration reaches a local minimum over the nondominated set. Then a cutting plane is inserted into the problem and another direction, if one can be found, that maximally minimizes the objective under consideration is employed. Although the method is heuristic, computational experience shows that much better estimates of the nadir criterion values can be obtained than from payoff tables.