When we have several different objective functions, and we are not sure how to combine them into a single objective function that describes our preferences, it’s reasonable to generate the Pareto set, which is the set of all alternatives that cannot be improved with respect to all the given objectives. This whole set of possible alternatives should help us make our decision. For a single objective function, the Pareto set is simply the set of all alternatives for which this objective function attains its optimal value. Since optimization is thus a particular case of the problem of computing the Pareto set, it is natural to generalize known optimization algorithms to the Pareto set problem.

One of the efficient optimization techniques is the branch-and-bound technique, in which we dismiss a branch when the corresponding value of the minimized function exceeds a certain bound. For multi-objective optimization, it is reasonable to consider a set of bounds, one for each objective function. For the biobjective spanning tree problem, this idea improved speed by an order of magnitude, but it has not been tested on other problems.

The authors of this paper demonstrate that the idea of using a set of bounds also works for the biobjective binary knapsack problem, when we use dynamic programming. To further improve the performance, they compute several points from the Pareto set and dismiss alternatives dominated by these points. This drastically limits the search space.

The authors propose a promising new approach. I strongly recommend this paper to all readers interested in new techniques for multi-objective optimization.